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
5
-
$\begingroup$ One word: performance. $\endgroup$– swineoneFeb 28 at 3:03
-
4$\begingroup$ How about en.wikipedia.org/wiki/Very_smooth_hash $\endgroup$– ponchoFeb 28 at 3:12
-
$\begingroup$ Thank you so much @poncho $\endgroup$– constantineFeb 28 at 3:15
-
$\begingroup$ Now, I wonder if there is a hard problem that CRHF cannot be constructed on it $\endgroup$– constantineFeb 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$– MarkMar 1 at 3:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$– ckamathFeb 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$– ckamathMar 23 at 7:59