Безопасность хеш-функций

Учитывая хэш-функцию H, как доказываются такие свойства, как устойчивость к коллизиям, устойчивость к целевым столкновениям, однонаправленность и негибкость? Я читал о хеш-функции и заявлял, что она устойчива к коллизиям, но как они формально доказаны? Если хэш-функция удовлетворяет всем свойствам, будет ли она действовать как модель случайного оракула?

Вы не можете доказать эти свойства из аксиом ZF. Например, для однонаправленности это означало бы, что $FNP\neq FP$ и поэтому $P\neq НП$, которая известна как трудная задача.

Традиционный способ рассматривать хеш-функцию как устойчивую к коллизиям, одностороннюю и т. д. — это публично предложить ее и подождать и посмотреть, не обнаружили ли криптоаналитики атаку (конечно, вы должны быть уверены, что люди заинтересуются это - потому что есть большая награда например).

Вы также можете построить хеш-функцию на основе уже хорошо изученной хеш-функции (например, SHA-3) и доказать, что свойства безопасности хорошо изученной хэш-функции подразумевают свойства безопасности новой; мы называем этот тип аргументов доказуемой безопасностью.