6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Are you looking for $k$ collisions of pairs or one collision of at least $k$ inputs? $\endgroup$
    – Elias
    May 28, 2018 at 21:24
  • $\begingroup$ $k$ collisions on $O(\sqrt{k\times n})$ pairs $\endgroup$
    – Daniel
    May 28, 2018 at 21:28
  • 1
    $\begingroup$ 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. $\endgroup$ May 28, 2018 at 22:39
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    May 28, 2018 at 22:42
  • $\begingroup$ @FutureSecurity, there are multicollision based attacks on hash functions, so I disagree that it's more suited to math stackexchange. $\endgroup$
    – kodlu
    May 28, 2018 at 23:36

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This was such an elegant solution, I must observe. $\endgroup$
    – Daniel
    May 29, 2018 at 16:34

Your Answer

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

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