Cryptography Reference
In-Depth Information
Psuedorandom walks
all
L
instances of the DLP, using Pollard rho with distinguished points, in roughly
√
2
rL
group operations. A crucial trick, attributed to Silverman and Stapleton, is that once the
i
th
DLP is known one can re-write all distinguished points
g
a
h
i
in the form
g
a
. As noted by
Hitchcock, Montague, Carter and Dawson [
260
], one must be careful to choose a random
walk function that does not depend on the elements
h
i
(however, the random starting points
do depend on the
h
i
).
Exercise 14.2.20
Write down pseudocode for the Kuhn-Struik algorithm for solving
L
instances of the DLP, and explain why the algorithm works.
Section
14.2.5
explains why the rho algorithm with distinguished points can be easily
parallelised. That section also discusses a number of practical issues relating to the use of
distinguished points.
Cheon, Hong and Kim [
124
] speed up Pollard rho in
F
p
by using a “look ahead”
strategy; essentially they determine in which partition the next value of the walk lies,
without performing a full group operation. A similar idea for elliptic curves has been used
by Bos, Kaihara and Kleinjung [
84
].
14.2.5 Towards a rigorous analysis of Pollard rho
Theorem
14.2.14
is not satisfying since Heuristic
14.2.13
is essential
ly equ
ivalent to the
statement “the rho algorithm has expected running time (1
o
(1))
√
πr/
2 group opera-
tions”. The reason for stating the heuristic is to clarify exactly what properties of the
pseudorandom walk are required. The reason for believing Heuristic
14.2.13
is that exper-
iments with the rho algorithm (see Section
14.4.3
) confirm the estimate for the running
time.
We now give a brief survey of theoretical results on the rho algorithm. The main results
for the original rho walk (with
n
S
=
+
3) are due to Horwitz and Venkatesan [
266
], Miller
and Venkatesan [
382
] and Kim, Montenegro, Peres and Tetali [
302
,
301
]. These works
all assume that the partition function
S
is a truly random function. The basic idea is to
define the
rho graph
, which is a directed graph with vertex set
and an edge from
x
1
to
x
2
if
x
2
is the next step of the walk when at
x
1
. Fix an integer
n
. Define the distribution
D
n
on
g
, running the walk for
n
steps, and recording the final point in the walk. The crucial property to study is the
mixing
time
, which, informally, is the smallest integer
n
such that
g
obtained by choosing uniformly at random
x
1
∈
g
D
n
is “sufficiently close” to the
uniform distribution. For these results, the squaring operation in the original walk is crucial.
The main re
s
ult of [
301
] is that the Pollard rho algorithm solves the DLP with probability
1
/
2in
O
(
√
r
) group operations, where the implied constant in the
O
is not specified. Note
that the idealised model of
S
being a random function is not implementable with constant
(or even polynomial) storage.
Sattler and Schnorr [
461
] and Teske [
542
] have considered the additive rho walk. One
key feature of their work is to discuss the effect of the number of partitions
n
S
. Sattler and
