11
$\begingroup$

Does the existence of a PRF/PRG/one way function imply the existence of a hash function? I did not find a proof of the existence of a cryptographic hash function, so I want to know whether it is based the same axiom (the PRG axiom)?

$\endgroup$
13
$\begingroup$

There is a black-box separation between one-way functions and collision resistant hash functions. This was proven at Eurocrypt 1998 by Dan Simon, in the paper entitled Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?. Of course, this doesn't mean that it's not possible using non-black-box reductions, but no one knows how to do this.

| improve this answer | |
$\endgroup$
7
$\begingroup$

To complement Yehuda Lindell's answer, if you need a property weaker than collision resistance (e.g. target collision resistance), then the existence of such hash function is equivalent to the existence of one-way functions, which is equivalent to the existence of prgs.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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