Cryptography Reference
In-Depth Information
P
(no collision)=
1
2
n
1
2
n
1
1
2
t
−
1
−
−
···
−
2
n
1
2
n
t
−
1
i
=1
i
=
−
We recall from our calculus courses that the approximation
e
−
x
≈
1
−
x
,
holds
1
since
i
/
2
n
<<
1. We can approximate the probability as:
t
1
i
=1
e
−
2
n
−
P
(no collision)
≈
1+2+3+
···
+
t
−
1
e
−
≈
2
n
The arithmetic series
1 + 2 +
···
+
t
−
1 =
t
(
t
−
1)
/
2
,
is in the exponent, which allows us to write the probability approximation as
t
(
t
−
1)
2
·
2
n
e
−
P
(no collision)
≈
.
Recall that our goal is to find out how many messages (
x
1
,
x
2
,...,
x
t
) are needed to
find a collision. Hence, we solve the equation now for
t
. If we denote the probability
of at least one collision by
λ
= 1
−
P
(no collision), then
t
(
t
−
1)
2
n
+1
e
−
λ
≈
1
−
t
(
t
1)
2
n
+1
−
ln (1
−
λ
)
≈−
2
n
+1
ln
.
1
t
(
t
−
1)
≈
1
−
λ
Since in practice
t
>>
1, it holds that
t
2
≈
t
(
t
−
1) and thus:
2
n
+1
ln
1
≈
t
1
−
λ
2
(
n
+1)
/
2
ln
.
1
t
≈
(11.1)
1
−
λ
1
This follows from the Taylor series representation of the exponential function:
e
−
x
= 1
−
x
+
x
2
/
2!
x
3
/
3! +
−
···
for
x
<<
1.
