7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The constant function is also a one-way function. $\endgroup$ – ratchet freak Oct 16 '17 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 Oct 16 '17 at 21:11
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much for the reference and the explanation! $\endgroup$ – mti Oct 16 '17 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 Oct 16 '17 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 Oct 16 '17 at 21:18

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.