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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
