0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Usually, the size of the keyspace would make precomputing collisions for all keys infeasible $\endgroup$
    – meshcollider
    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

0

Reset to default

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.