In general, can we construct a collision resistant hash function from a one-way function?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ The constant function is also a one-way function. $\endgroup$– ratchet freakOct 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$– MaeherOct 16, 2017 at 21:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$– mtiOct 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$ 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$– MaeherOct 16, 2017 at 21:18