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?

  • 1
    $\begingroup$ Usually, the size of the keyspace would make precomputing collisions for all keys infeasible $\endgroup$ Mar 1, 2022 at 3:49
  • $\begingroup$ 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... $\endgroup$
    – driewguy
    Mar 1, 2022 at 3:59
  • $\begingroup$ Keyed hash functions provides more than the collision, they are candidate of PRFs... $\endgroup$
    – kelalaka
    Mar 1, 2022 at 6:18
  • 1
    $\begingroup$ The keyspace is generally chosen to be superpolynomial. While this does not stop a nonuniform attacker from precomputing a collision for every key, it stops them from passing those collisions to the algorithm as part of their (polynomially bounded) nonuniform advice. $\endgroup$
    – Maeher
    Mar 1, 2022 at 8:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.