Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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).
