Cryptography Reference
In-Depth Information
Se
dgewi
ck [
188
] and Exe
rc
ise 3.1.12 of Knuth [
308
]. The expected number of samples is
√
πN/
2
O
(1
/
√
N
).
We remind the reader of the meaning of expected value. Suppose the experiment of
sampling elements of a set
+
2
/
3
+
of size
N
until a collision is found is repeated
t
times and
each time
we cou
nt the number
l
of elements sampled. Then the average of
l
over all trials
tends to
√
πN/
2as
t
goes to infinity.
S
Exercise 14.1.2
Show that the num
ber of ele
ments that
nee
d to be selected from
S
to get
1
.
177
√
N
.
a collision with probability 1
/
2is
√
2log(2)
N
≈
Exercise 14.1.3
One may be interested in the number of samples required when one is
particularly unlucky. Determine the number of trials so that with probability 0.99 one has
a collision. Repeat the exercise for probability 0.999.
The name “birthday paradox” arises from the following application of the result.
Example 14.1.4
In a room containing 23 or more randomly chosen people, th
e probability
is
greater than 0
.
5 that tw
o people
have the same birthday. This follows from
2 log(2)365
≈
22
.
49. Note also that
π
365
/
2
=
23
.
944
....
Finally, we mention that the expected num
ber o
f samples from a set of size
N
until
k>
1 collisions are found is approximately
√
2
kN
. A detailed proof of this fact is given
by Kuhn and Struik as Theorem 1 of [
320
].
14.2 The Pollard rho method
Let
g
be a group element of prime order
r
and let
G
=
g
. The discrete logarithm problem
g
a
. In this section we assume (as
is usually the case in applications) that one has already determined that
h
(DLP) is: given
h
∈
G
to find
a
, if it exists, such that
h
=
.
The starting point of the rho algorithm is the observation that if one can find
a
i
,b
i
,a
j
,b
j
∈ Z
∈
g
/r
Z
such that
g
a
i
h
b
i
g
a
j
h
b
j
=
(14.1)
and
b
i
≡
b
j
(mod
r
) then one can solve the DLP as
g
(
a
i
−
a
j
)(
b
j
−
b
i
)
−
1
(mod
r
)
.
h
=
g
a
i
h
b
i
of elements in
G
by
The basic idea is to generate pseudorandom sequences
x
i
=
iterating a suitable function
f
:
G
→
G
. In other words, one chooses a starting value
x
1
and defines the sequence by
x
i
+
1
=
f
(
x
i
). A sequence
x
1
,x
2
,...
is called a
deterministic
pseudorandom walk
. Since
G
is finite there is eventually a collision
x
i
=
x
j
for some
1
i<j
as in equation (
14.1
). This is presented as a collision between two elements in
the same walk, but it could also be a collision between two elements in different walks.
If the elements in the walks look like uniformly and independently chosen e
lemen
ts of
G
then, by the birthday paradox (Theorem
14.1.1
), the expected value of
j
is
√
πr/
2.
≤
