# Collision resistance analysis

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?

• Usually, the size of the keyspace would make precomputing collisions for all keys infeasible Commented Mar 1, 2022 at 3:49
• 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... Commented Mar 1, 2022 at 3:59
• Keyed hash functions provides more than the collision, they are candidate of PRFs... Commented Mar 1, 2022 at 6:18
• 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. Commented Mar 1, 2022 at 8:49