We know that in the black-box sense, we cannot use one-way functions to construct Collision Resistant Hash Functions.I feel that in my impression, I have never seen CRHF based on integer factorization problem or RSA assumption

  • $\begingroup$ One word: performance. $\endgroup$
    – swineone
    Feb 28 at 3:03
  • 4
    $\begingroup$ How about en.wikipedia.org/wiki/Very_smooth_hash $\endgroup$
    – poncho
    Feb 28 at 3:12
  • $\begingroup$ Thank you so much @poncho $\endgroup$ Feb 28 at 3:15
  • $\begingroup$ Now, I wonder if there is a hard problem that CRHF cannot be constructed on it $\endgroup$ Feb 28 at 14:08
  • $\begingroup$ As a side note that wikipedia article is very funny --- when describing an asymptotic notion of security, it contains the line "This is considered a useless assumption for practice", and then describes a concrete security assumption. $\endgroup$
    – Mark
    Mar 1 at 3:22

1 Answer 1


Damgård constructed CRHFs from claw-free permutations, which can be based on integer factorisation (or even the discrete-log problem) [D]. That's the earliest one I am aware of (but someone feel free to correct me).

[D]: Damgård, Collision Free Hash Functions and Public Key Signature Schemes, Eurocrypt'87

  • $\begingroup$ thanks, Now, I wonder if there is a hard problem that CRHF cannot be constructed on it. $\endgroup$ Feb 28 at 14:09
  • $\begingroup$ Interesting. The concrete hardness assumptions I can think of also yield CRHFs. Will think about it. $\endgroup$
    – ckamath
    Feb 28 at 14:41
  • 1
    $\begingroup$ Feel free to ask a question about that, but yes, there are many! For example, we don't know how to build CRHFs from one-way functions (for a generic assumption), or from the learning parity with noise assumption (for a concrete assumption - except in the extremely low-noise regime). $\endgroup$ Feb 28 at 16:24
  • $\begingroup$ @ckamath, is there a CRHF based on graph isomorphism problem? I think maybe not $\endgroup$ Mar 21 at 12:03
  • $\begingroup$ Right, but then we don't know any crypto from GI (and it might as well turn out to be easy). $\endgroup$
    – ckamath
    Mar 23 at 7:59

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.