Hash Collision Problem

Let

$n$ be the output length in bits of a hash function

$h$, and

$t$ mutually distinct message

$(x_1,x_2,\cdots ,x_t)$ be randomly selected to test collision

$h(x_i)=h(x_j)$.

Estimate the probability of "at least one collision" to be

$\lambda$. Show that when

$n$ is large, the required number of messages is approximately

$$t\approx 2^{(n+1)/2}\sqrt{\ln \left(\frac{1}{1-\lambda }\right)}.$$

---

Assume

$t$ is fixed. The probability of no collision,

$1-\lambda$, is

$$1(1-\frac{1}{2^n})(1-\frac{2}{2^n})\cdots (1-\frac{t-1}{2^n}).$$

The Taylor series of

$e^{-x}$ at

$x=0$ suggests that

$e^{-x}\approx 1-x$. The probability can be expressed approximately as

$$1\cdot e^{-1/2^n}\cdot e^{-2/2^n}\cdot \cdots \cdot e^{-(t-1)/2^n},$$

or

$$\begin{array}{rl}1-\lambda & =\exp [-t(t-1)/2^{n+1}]\\ & \approx \exp [-t^2/2^{n+1}].\end{array}$$

Solving for

$t$ yields the resulting approximation.

---

For Birthday problem,

$n=\lg 365$ and

$\lambda =1/2$. Compute

$2^{(n+1)/2}=\sqrt{730}$. Inserting them into above result yields

$$t=\sqrt{730}\cdot \sqrt{\ln 2}=22.49\cdots .$$

In general, when there are

$d$ choices, we anticipate 50% chance of presence of collisions if the number of random tests is above

$$2^{(\lg d+1)/2}\sqrt{\ln 2}=1.17\sqrt{d}=O(\sqrt{d}).$$