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$.
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) &amp;=\frac{n}{n-t+1} W_1(n-t+1,p)\\
&amp;=\frac{n}{n-t+1}\sqrt{2 \ln(1/p) (n-t+1)}\\
&amp;=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.