Join Log in
Score:0
driewguy avatar Crypto

Collision resistance analysis

vn flag
driewguy

I am learning about collision resistance security notion of hash functions. However, I got confused when collision resistance experiment started using "keyed" hash functions in the experiment (and also in other similar experiments). This is a small extract from Introduction to Modern Cryptography by Katz and Lindell :

The collision finding experiment:
1. A key s is generated by running Gen(1^n).
2. The adversary A is given s, and outputs x; x^0
3. The output of the experiment is defined to be 1 iff x \ne x0 and H^s(x) = H^s(x0).

I understand that without "keyed" hash function, in formal analysis of the security, adversary can "cheat" by pre-computing collisions (before the experiment). But even after adding "key", adversary can "cheat" by pre-computing collisions for all "keys". And during experiment, adversary can output collisions based on the key. What did "keyed" hash function solve in formal analysis?

45
0 + 0
meshcollider avatar
gb flag
meshcollider
Usually, the size of the keyspace would make precomputing collisions for *all* keys infeasible
1
Reply
driewguy avatar
vn flag
driewguy
But by that argument, shouldn't "cheating" by pre-computation under non-keyed hash function be infeasible as well? Since, time complexity of pre-computation would be exponential in terms of its range space...
0
Reply
kelalaka avatar
in flag
kelalaka
Keyed hash functions provides more than the collision, they are candidate of PRFs...
0
Reply
cn flag
Maeher
The keyspace is generally chosen to be superpolynomial. While this does not stop a nonuniform attacker from pre*computing* a collision for every key, it stops them from passing those collisions to the algorithm as part of their (polynomially bounded) nonuniform advice.
1
Reply
ธงชาติไทย
Elon Musk
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.