Score:2

Is there a CRHF based on integer factorization problem or RSA assumption

cn flag

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

swineone avatar
ru flag
One word: performance.
poncho avatar
my flag
How about https://en.wikipedia.org/wiki/Very_smooth_hash
constantine avatar
cn flag
Thank you so much @poncho
constantine avatar
cn flag
Now, I wonder if there is a hard problem that CRHF cannot be constructed on it
Mark avatar
ng flag
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.
Score:2
ag flag

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

constantine avatar
cn flag
thanks, Now, I wonder if there is a hard problem that CRHF cannot be constructed on it.
ckamath avatar
ag flag
Interesting. The concrete hardness assumptions I can think of also yield CRHFs. Will think about it.
Geoffroy Couteau avatar
cn flag
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).
constantine avatar
cn flag
@ckamath, is there a CRHF based on graph isomorphism problem? I think maybe not
ckamath avatar
ag flag
Right, but then we don't know any crypto from GI (and it might as well turn out to be easy).
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.