Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am reading the birthday attack in wikipedia.

We consider the following experiment. From a set of $H$ values we choose $n$ values uniformly at random thereby allowing repetitions. Let $p(n; H)$ be the probability that during this experiment at least one value is chosen more than once. This probability can be approximated as $$p(n:H)\approx 1-e^{-n(n-1)/2H}$$

My question: Where does that $-e^{-n(n-1)/2H}$ value come from ?

share|improve this question
    
That 2H looks weird. Shouldn't that be in the denominator? –  CodesInChaos Jul 16 '13 at 21:16
    
@CodesInChaos Look at the linked Wikipedia article. It's ambiguous with $/$ and $\cdot$ priority. –  nightcracker Jul 16 '13 at 21:21
add comment

3 Answers

Let's first calculate the chance that every value is unique.

The chance of two values picked being unique is $H - 1 \over H$ because when picking the second value you only have $H - 1$ unique picks left, with one pick being non-unique. Picking a third number has a chance of $H - 2 \over H$ to be unique, so the total chance of picking 3 unique numbers is ${H - 1 \over H} \times {H - 2 \over H}$. This can be continued so that the chance of picking $n$ unique values is:

$${H - 1 \over H} \times {H - 2 \over H} \times \cdots \times {H - (n - 2) \over H} \times {H - (n - 1) \over H}$$

This is exactly the same as the limit for the birthday paradox.

Then a bit more math is required. An approximation is used. For $x \leq 1$ the taylor series of $e$ gives an approximation:

$$e^x \approx 1 + x$$

Then note the following:

$${H - 1 \over H} = 1 - {1 \over H} \approx e^{-{1 \over H}}$$

Then we rewrite the calculate as such:

$$e^{-{1 \over H}} \times e^{-{2 \over H}} \times \cdots \times e^{-{n - 2 \over H}}\times e^{-{n - 1 \over H}} =$$ $$e^{-{1 + 2 + \cdots + n-2 + n-1 \over H}} =$$ $$e^{-{n(n-1)/2 \over H}} = e^{-{n(n-1) \over 2H}} $$

That is the probability that every value picked is unique. If not every value is unique there must be a collision, therefore the chance of a collision is:

$$p(n:H) \approx 1−e^{-{n(n-1) \over 2H}}$$

This is also the value the linked wikipedia article means, but it's a bit ambiguous with $/$ and $\cdot$ priority rules.

share|improve this answer
add comment

Here is a slightly different approach: The total number of ways to pick $n$ numbers among $H$ value allowing repetition (and with the order of picking counted in) is $A=H^n$. The number of ways to pick without repetitions is $B=\frac{H!}{(H-n)!}.$

Clearly, the probability you want to compute is $(A-B)/A=1-B/A$. Now, does $B/A$ contains the exponential you look for ? Using Stirling's formula: $$x!\approx \sqrt{2\pi x}(x/e)^x.$$ We see that: $$ A/B\approx \sqrt{\frac{H-n}{H}}\left(\frac{H-n}{H}\right)^{H-n}e^n. $$

Taking logarithm, we find: $$\log(A/B)\approx (H-n+1/2)\log(1-n/H)+n\approx -(H-n+1/2)(n/H+(n/H)^2/2)+n$$

Develop and remove low order terms to obtain $\log(A/B)\approx n(n-1)/2H$.

Putting everything together indeed yields $$p(n:H)\approx 1-e^{\frac{n(n-1)}{2H}}.$$

The main advantage of this approach is that it avoids taking the product of many approximations (as in nightcracker's answer) which, in general, requires great care.

share|improve this answer
add comment

Here's yet another similar way to get this approximation.

Consider every pairing of n elements from H, ignoring elements paired with themselves but not requiring that the elements be unique. i.e. $Let\ H_n=\{n\ elements\ chosen\ from\ H\}, P_n=\{(h_i,h_j) | h_i,h_j \in H_n\ and\ i\ne j\}$.Each element can be matched with any other element, so there are $\frac{n(n-1)}{2}$ pairs in $P_n$, rejecting $(h_b, h_a)$ if $(h_a,h_b)$ is already present. The probability of any pair not being a match is $(1-1/H)$.

Notice that these pairs being nonmatches are not independent events since if $(h_1,h_2)$ is not a match and $(h_2,h_3)$ is not a match, the probability of $(h_1,h_3)$ not being a match is $(1-\frac{1}{H-1})$.

This approximation treats these as independent events. In that case,
Prob(no_matches_in_$P_n$)=$\ (1-1/H)^{n*(n-1)/2}=(1-1/H)^{H*n(n-1)/(2H)}\approx e^{-n*(n-1)/(2H)}$
Since $\lim_{H \to \infty}(1-1/H)^H=e^{-1}$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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