Let $f$ be a collision resistant function i.e. it is computationally impossible to find $x_0, x_1$ such that $f(x_0) = f(x_1)$. If a computationally bounded adversary demonstrates that he knows some $x_0$ and $f(x_0)$, in what sense is he unable to determine $x_1$?

My instinct is that he can do no better than choosing a random guess from the domain of $f$ but is this how collision resistance is defined? Moreover, if $f$ has a trapdoor, is the definition still the same i.e. collision resistance implies that either the adversary knows the trapdoor or he can do no better than pick a random element from the domain of $f$?

I apologize that this is a bit of a yes/no question although if the answer is no, then there is more to say!

EDIT: Alternatively, what is the mathematical statement that captures the idea that there is no efficient algorithm to find a collision?


2 Answers 2


Let the range $Y$ of the function $f$ have size $N$ A collision resistant function cannot be better than an ideal function which maps uniformly into $Y$ since collision probability is minimized by the uniform distribution. Thus, given $(x_0,f(x_0))$ the number $k$ of random points $x_i\neq x_0$ that must be tried before the probability that $f(x_i)=f(x_0)$ is significant, say at least $1/2$ is $k\approx \sqrt{\ln 2 N}$ by the birthday paradox.

If necessary see @fgrieu's detailed post on the mathematics of the birthday paradox here.

  • $\begingroup$ Thank you. Could you also comment on the following: When one says there is no efficient algorithm to find a collision, what is the mathematical definition this corresponds to? $\endgroup$ Commented Oct 11, 2019 at 10:06
  • 1
    $\begingroup$ Let the output space have bitlength $b,$ hence $b=\log_2 N.$ The algorithm in the answer needs approximately $\sqrt{N}=2^{b/2}$ queries before finding a collision with probability $1/2.$ This quantity is exponential in the input size (bitlength) $b,$ hence inefficient. If it could be found with $b^c$ trials, for constant $c$, it would have polynomial complexity in the bitlength, hence efficient. $\endgroup$
    – kodlu
    Commented Oct 11, 2019 at 12:18
  • $\begingroup$ Ah I see - so no matter what algorithmthe attacker uses, the complexity is the same as a random guess attack? Thank you! $\endgroup$ Commented Oct 11, 2019 at 12:29
  • $\begingroup$ Please keep in mind that if the adversary has full control about the definition of f and the choose of $x_0$ and $x_i$ this requirement is very hard to fulfill since the adversary can define any two $x_0$ and $x_1$ such that $h(x_0) = h(x_1)$. There has to be a mechanism which makes it hard for the adversary to define the functions f like that. $\endgroup$ Commented Oct 11, 2019 at 13:48
  • $\begingroup$ @MartinKromm, I can choose $f$ instead of the adversary and then this is fine, no? The point is then that $x_1$ is indistinguishable from a random string (in the domain of $f$) for the adversary. $\endgroup$ Commented Oct 11, 2019 at 14:43

Defining a hash function formally is not an easy task. There are even entire papers covering that formalization, especially if there is a requirement that the function should be unkeyed (see for the keyed variant below).

The most popular variant to formalize hash functions are the use of choosing a hash function chosen from a family of hash functions HashFamily(KeyGen, Hash):

  • Given security parameter $1^n$, algorithm KeyGen outputs a key k.
  • Given key k, a family of hashes $H := \{h_0, ..., h_{2^n - 1}\}$ and a message m, algorithm Hash outputs $h_k(m)$ with $h_k \in H$.

Now consider the following game Col:

  • The adversary A is given H and a random key k.
  • The adversary A outputs $m_1$ and $m_2$.
  • The adversary A wins if $h_k(m_1) = h_k(m_2)$ and $m_1 \neq m_2$.

Collision resistant means that $\forall PPT A: Pr[Col(A) = 1] \leq negl(n)$.

The above game implies that the adversary A can compute $Hash(k, H, \cdot)$ by himself. However, since the adversary is computationally bounded, he can only query a limited number of messages (if the adversary is unbounded, then the adversary always wins the game unless $h_\cdot$ is injective of course).

PPT A means probabilistic polynomial time algorithm. That means that given some randomness r, algorithm A computes x using any strategy in $O(n^z)$ (with z being constant and independent of the input size).

I would also recommend you reading Introduction to Modern Cryptography by Katz & Lindell. There is the topic explained in more detail.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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