Skip to main content
Cryptography

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • 1
    $\begingroup$ Lets take some more practical question. Say we want to find a collision for a single hash function, then the birthday attack gives us a somewhat efficient way to find this collision. Does this change when talking about hash families? Because when we are given a key K, then its just the same as finding a collision for a single hash function, right? $\endgroup$ Commented Jan 3, 2024 at 14:38
  • 2
    $\begingroup$ @Wouter: well, if you take a single member of a hash function family (e.g. the one with publicly known key $K$), it is effectively a single hash function. $\endgroup$ Commented Jan 3, 2024 at 14:52
  • $\begingroup$ I think I see where I made my mistake. To break collision resistance, a polynomial time algorithm has to exist that outputs two values $x_1$ and $x_2$ such that $h(x_1)=h(x_2)$. I assumed that such algorithms start with 0 knowledge, such as the birthday attack. However, as I now understand it, we can define this algorithm as "output the two colliding values $x_1$ and $x_2$", which must exist due to the pigeonhole principle. For a keyed hash function this is not possible since for different keys the colliding values are not the same. Is this correct? $\endgroup$ Commented Jan 3, 2024 at 18:23
  • 3
    $\begingroup$ @Wouter: yes, that is correct. One way to look at it: the $K$ variable is a way to exclude some information about the hash function (such as a preexisting collision), while continuing to include other information (such as the internal structure of the hash function, which the attacker is free to use) $\endgroup$ Commented Jan 3, 2024 at 18:33
  • 1
    $\begingroup$ @Wouter: we assume that the program is concise (that is, of reasonable size), and so it cannot contain entries for every possible key (and so the set of keys doesn't have to be infinite, just large) $\endgroup$ Commented Jan 4, 2024 at 14:39