In general, can we construct a collision resistant hash function from a one-way function?

  • $\begingroup$ The constant function is also a one-way function. $\endgroup$ Commented Oct 16, 2017 at 15:11
  • 6
    $\begingroup$ @ratchetfreak No, it is most certainly not. For the constant function it is absolutely trivial to find preimages. $\endgroup$
    – Maeher
    Commented Oct 16, 2017 at 21:11

1 Answer 1


Simon [Sim98] showed that is not possible to build a collision-resistant hash function from a one-way permutation (which is a stronger statement) in a black-box manner .

The main idea is to use the so-called oracle-separation technique. You can read more about it either here or in this survey.

[Sim98]: Daniel Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? Eurocrypt'98.

  • $\begingroup$ Thank you very much for the reference and the explanation! $\endgroup$
    – mti
    Commented Oct 16, 2017 at 9:24
  • $\begingroup$ What about the following construction. Apply the one way permutation to a different collision resistant hash function. Obviously cheating but I wonder how this doesn't violate the proof. $\endgroup$
    – Meir Maor
    Commented Oct 16, 2017 at 17:57
  • 2
    $\begingroup$ @MeirMaor Well, the way an oracle separation works makes sure that there is no hash function you could use in such a manner, unless it can be constructed from the OWP. Basically you introduce an oracle into the world that breaks all crypto. And in the next step you reintroduce a OWP as another oracle. All hash functions that may or may not exists in the real world are destroyed in the first step. $\endgroup$
    – Maeher
    Commented Oct 16, 2017 at 21:18

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.