In collision-resistant hash function, first, a hash function is sampled and the adversary is allowed to pick a collision $(x, x')$ s.t. $H(x) = H(x')$ and $x \neq x'$.

In a universal one-way hash function, first, the adversary picks $x$, and then a hash function is sampled, and then the adversary is supposed to find $x'$ s.t. $H(x) = H(x')$.

Is there any example of a universal one-way hash function that is not collision resistant?

  • $\begingroup$ Universal hash functions are keyed; that is, that have a random input that determines actual hash mapping. If the adversary learns the key, it's (with most universal hash functions in use) easy. In your example, what does the adversary learn? Does he learn the value $H_k(x)$, and from that, is asked to find an $x'$ s.t. $H_k(x')$ is that same value? $\endgroup$ – poncho Nov 7 '20 at 22:27
  • 1
    $\begingroup$ @poncho There is a difference between a universal and universal one-way hash function. So, this is different. $\endgroup$ – Yehuda Lindell Nov 8 '20 at 6:52

One can construct such an example artificially. Denote the key to the hash function by $s$ (and recall that this key is public). Now, let $H$ be any universal one-way hash function, and define $H'_s(s) = H'_s(s+1)$. This requires changing just one point in $H$, and so is easy.

Notice that $H'$ is clearly not collision resistant: given $s$, just output the pair $(s,s+1)$. However, I argue that $H'$ is still a universal one-way hash function (often called target collision-resistant). The reason for this is that the only way that this change to $H$ can help is if the adversary chooses $x=s$ or $x=s+1$ before the key is chosen. However, this can only happen with negligible probability, unless the key space is polynomial in size. However, if the key space is so small, then the hash function cannot be secure anyway (basically, in such a case, you can just get rid of the key).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.