# Finding k collisions on hash function

Let $n$ be the size of the image-space of a hash function $H$.

It is known that you can find a collision on $H$ in $O(\sqrt{n})$ time (by birthday paradox).

How can I show that, in order to find $k$ collisions, it is needed only $O(\sqrt{k\times n})$ time?

I have no idea yet... I guess this happens because after you look $O(\sqrt{n})$ times for collisions, the probability grows significantly, but I don't know where I can apply $k$.

• Are you looking for $k$ collisions of pairs or one collision of at least $k$ inputs? May 28, 2018 at 21:24
• $k$ collisions on $O(\sqrt{k\times n})$ pairs May 28, 2018 at 21:28
• This question can be reinterpreted as a request for a solution to / explanation of a modified birthday problem. That sounds more suited to the math stackexchange. May 28, 2018 at 22:39
• I guess that once you've found a collision that you don't toss away all the previous hash results. That's something you need to put into a formula to get to the end result. May 28, 2018 at 22:42
• @FutureSecurity, there are multicollision based attacks on hash functions, so I disagree that it's more suited to math stackexchange. May 28, 2018 at 23:36

I will try to give a simple proof of the expectation. Define $W_t(n,p)$ as the expected number of trials required to find the $t^{th}$ collision in a set of size $n$ with probability $p.$

Normally, for $W_1(n,p),$ the standard birthday problem with fail probability $p,$ which gives $W_1 = c \sqrt{n},$ with $c$ obtained by solving $$\exp\left(\frac{-k(k-1)}{2n}\right) = p = \exp( \ln(p))=\exp(-\ln (1/p))\tag{1}\label{eq1}$$ for $p=1/2,$ and letting the $k$ obtained to be $W_1(n,p).$

So we're after the total expected wait, call it $$T_k=W_1(n,p_1)+W_2(n,p_2)+\cdots+W_k(n,p_k)$$ with the assumption that $k$ is much much smaller than $n.$ Let $W_i$ denote the expected wait for the $t^{th}$ collision with probability $p_t,$ which we shall select later.

Solving $\eqref{eq1}$ approximately gives $$W_1(n,p)= \sqrt{2 \ln(1/p) n}.$$ Now note that, \begin{align} W_t(n,p) &=\frac{n}{n-t+1} W_1(n-t+1,p)\\ &=\frac{n}{n-t+1}\sqrt{2 \ln(1/p) (n-t+1)}\\ &=O\left(\sqrt{2 \ln(1/p) (n-t+1)}\,\right), \end{align} (both sides are expectations) since there are already $t-1$ collisions and $t$ is much smaller than $n.$ To explain further, this means that you want the next collision in the remaining $n-(t-1)$ positions but the probability of falling into one of those positions is $q=(n-t+1)/n$ so it takes an expected $1/q$ trials.

Now we can write $$T_k=O\left(\sum_{t=0}^k \sqrt{2 \ln(1/p_t) (n-t+1)}\right),$$ but due to the multistage nature of the argument, the overall probability that this sequence of waiting times fails to find the $k$th collision is the product $$p_1p_2 \cdots p_k.$$ We want this probability to be $1/2,$ as in the original birthday problem, which we can ensure by choosing $p_t=(1/2)^{1/k},$ for all $t.$ This can be optimized a bit by putting slowly falling probabilities on later epochs and keeping the product of the probabilities fixed, but it won't make a difference to the $O(\cdot)$ answer. Since $\ln(2^{1/k})=k^{-1}\ln 2,$ we have

$$T_k=O\left(\sum_{t=0}^k \sqrt{2 \ln(2) k^{-1}(n-t+1)}\right)= \sqrt{k} \times O\left(\sqrt{ (n+1)}\right),$$ which gives (since there are $k$ terms in the sum and a $k^{-1/2}$ multiplying each term) $$T_k=O(\sqrt{nk})$$ as required.

A non-rigorous argument goes: there are $m(m-1)/2$ distinct subsets with two elements in a set with $m$ elements. Having hashed $m$ distinct values, that's $m(m-1)/2$ potential collisions. Each has probability $1/n$ if we model the hash as a uniformly random oracle. If these probabilities were independent (they are not), we could compute the expected number of collisions $k$ as the product of potential collisions times their probability, giving $m(m-1)/2n=k$, hence $m\approx\sqrt{2n\cdot k}$ for large $m$, hence effort $O(\sqrt{n\cdot k})$ to compute the $m$ hashes.

That approximation holds quite well at least as long as collisions between three values remain unlikely, that is for $m\ll n^{2/3}$ (perhaps more, but that's seldom useful in cryptography).

• This was such an elegant solution, I must observe. May 29, 2018 at 16:34