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
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$.
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).
