Cryptography Reference
In-Depth Information
> for r in {20, 23, 30, 40, 50, 60} do
print(r, p(365., r), ep(365., r))
end do;
20, 0.4114383837, 0.4058051274
23, 0.5072972342, 0.5000017522
30, 0.7063162428, 0.6963200177
40, 0.8912318099, 0.8819900460
50, 0.9703735796, 0.9651312541
60, 0.9941226609, 0.9921662587
In each of the preceding rows, the first number represents
r
, the second is the real
probability of a collision and the third the estimate of this probability given by the
preceding theorem. We see that the probability for
r
=
23 is indeed greater than
(and close to) 1
23 are large
enough for the estimate to be accurate. Note that the estimate given by the theorem
is very close already for these relatively small numbers and also that the probability
of a collision grows quickly with
r
and is already near 90% for 40 people and over
99% for 60 people.
/
2 as predicted by the theorem, so that
n
=
365 and
r
=
There are many versions of the birthday paradox and another one, with crypto-
graphic interest in relation to collisions of hash functions, arises when we consider
two sets of strings and ask about the probability of a collision between a member of
the first set and a member of the second set. We will restrict ourselves to the case in
which both sets have the same size, which is enough for our purposes.
Theorem 5.5
Suppose that two sets of r integers between
1
an
d n are chosen at
random with uniform probability distribution, where r
√
n. If n is large, the
<
e
−
r
2
/
2
n
. Moreover, this probability is
probability that the two sets o
v
erlap is
≥
1
−
83
√
n.
close to
1
/
2
when r
≈
0
.
<
√
n
, it is likely that the
r
integers of each set are all different and
we assume that this is the case, but the argument will work even if there are a few
repeated elements in the sets.
3
We observe that the probability that one given element
of the first set is different from each element in the second set is
Proof
Since
r
1
r
and hence
(
1
−
n
)
r
2
1
the probability
q
that the two sets are disjoint is
(
1
−
n
)
. Using the approximation
e
−
x
1
−
x
≈
for
x
=
1
/
n
we obtain that the probability
p
that the two sets overlap is
e
−
r
2
/
n
p
=
1
−
q
≈
1
−
.
r
2
Now, equating this value to 1
/
2 we obtain ln 2
=
/
n
which, in turn, gives:
√
n
ln 2
83
√
n
r
=
≈
0
.
.
3
Note that, strictly speaking, a set cannot have repeated elements and we are really dealing here
with
multisets
, which are similar to sets except for the fact that they can contain multiple instances
of each member. But we shall commit abuse of language and speak of sets anyway.
