Cryptography Reference
In-Depth Information
It is important that the function
f
be designed so that one can efficiently compute
a
i
,b
i
∈ Z
g
a
i
h
b
i
. The next step
x
i
+
1
depends only on the current step
x
i
and not on (
a
i
,b
i
). The algorithms all exploit the fact that when a collision
x
i
=
/r
Z
such that
x
i
=
x
j
occurs
then
x
i
+
t
=
. Pollard's original proposal used a cycle-finding method due
to Floyd to find a self-collision in the sequence; we present this in Section
14.2.2
. A better
approach is to use distinguished points to find collisions; we present this in Section
14.2.4
.
x
j
+
t
for all
t
∈ N
14.2.1 The pseudorandom walk
Pollard simulates a random function from
G
to itself as follows. The first step is to
decompose
G
into
n
S
disjoint subsets (usually of roughly equal size) so that
G
=
S
0
∪
S
1
∪···∪
S
n
S
−
1
. Traditional textbook presentations use
n
S
=
3 but, as explained
in Section
14.2.5
, it is better to take larger values for
n
S
; typical values in practice are 32,
256 or 2048.
The sets
S
i
are defined using a selection function
S
:
G
→{
0
,...,n
S
−
1
}
by
S
i
=
{
g
∈
G
:
S
(
g
)
=
i
}
. For example, in any computer implementation of
G
one represents
G
as a unique
2
an element
g
∈
binary string
b
(
g
) and interpreting
b
(
g
) as an integer one
=
could define
S
(
g
)
b
(
g
)(mod
n
S
) (taking
n
S
to be a power of 2 makes this computation
especially easy). To obtain different choices for
S
one could apply an
F
2
-linear map
L
to the sequence of bits
b
(
g
) so that
S
(
g
)
L
(
b
(
g
)) (mod
n
S
). These simple methods can
be a poor choice in practice as they are not “sufficiently random”. Some other ways to
determine the partition are suggested in Section 2.3 of Teske [
543
] and Bai and Brent [
23
].
The strongest choice is to apply a hash function or randomness extractor to
b
(
g
), though
this may lead to an undesirable computational overhead.
=
g
u
j
h
v
j
Definition 14.2.1
The
rho walks
are defined as follows. Precompute
g
j
=
for
0
≤
j
≤
n
S
−
1 where 0
≤
u
j
,v
j
<r
are chosen uniformly at random. Set
x
1
=
g
.The
original rho walk
is
x
i
if
S
(
x
i
)
=
0
x
i
+
1
=
f
(
x
i
)
=
(14.2)
x
i
g
j
if
S
(
x
i
)
=
j, j
∈{
1
,...,n
S
−
1
}
.
The
additive rho walk
is
x
i
+
1
=
f
(
x
i
)
=
x
i
g
S
(
x
i
)
.
(14.3)
An important feature of the walks is that each step requires only one group operation.
Once the selection function
S
and the values
u
j
and
v
j
are chosen, the walk is deterministic.
Even though these values may be chosen uniformly at random, the function
f
itself is not
a random function as it has a compact description. Hence, the rho walks can only be
described as pseudorandom. To analyse the algorithm we will consider the expectation of
2
One often uses projective coordinates to speed up elliptic curve arithmetic, so it is natural to use projective coordinates when
implementing these algorithms. But to define the pseudorandom walk one needs a unique representation for points, so projective
coordinates are not appropriate. See Remark
13.3.2
.
