Given a Hash Function H, how are the properties such as collision resistance, target collision resistance, one wayness, and non-malleability proved? I have read about hash function and stating that it is collision-resistant but how are they formally proved? If a hash function satisfies all the properties will it act as a random oracle model?


1 Answer 1


You can't prove these properties from ZF axioms. For one-wayness, for example it would imply that $FNP\neq FP$ and thus $P\neq NP$, which is known as a hard problem.

The traditional way to consider a hash function as collision-resistant, one-way, etc is to publicly propose it and wait and see if crypt-analysts have found an attack (of course, you have to be sure that people will be interested by this - because there is a big reward for example).

You can also build a hash function based on an already well-studied hash function (like SHA-3), and prove that security properties of the well-studied hash function imply security properties of the new one; we call these type of arguments provable security.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.