Cryptography Reference
In-Depth Information
This is called the
four-k
ang
aroo algorithm
. Explain why the correct choice for the mean
step size is
m
0
.
375
√
2
w
and wh
y t
he he
u
ristic av
era
ge-case expected number of group
operations is approximately 1
.
714
√
w
=
2
√
2
3
1
.
818
√
w
.
=
Galbraith, Pollard and Ruprai [
219
] have combined the idea of Exercise 14.5.12 and the
Gaudry-Schost algorithm (see Section 14.7) to obtain an algorithm f
or
the discrete loga-
rithm problem in an interval of length
w
that performs (1
.
660
o
(1))
√
w
group operations.
+
14.5.6 Towards a rigorous analysis of the kangaroo method
Pollard [
438
] gave a detailed heuristic analysis of the kangaroo method using jumps
that are pow
er
s of two. His results suggest the expected running time is asymptotically
(2
o
(1))
√
w
group operations. Montenegro and Tetali [
390
] have analysed the kangaroo
method using jumps that are powers of 2, under the assumption that the selection function
S
is random and that the distinguished points are well-distribut
ed
. They prove that the
average-case expected number of group operations is (2
+
o
(1))
√
w
group operations. It is
beyond the scope of this topic to give the details of these papers.
+
14.6 Distributed kangaroo algorithm
Let
N
P
be the number of processors or clients. A naive way to parallelise the kangaroo
algorithm is to divide the interval [0
,w
)into
N
P
subintervals of size
w/N
P
and then run the
kangaroo
algorit
hm in parallel on each subinterval. This gives an algorithm with running
time
O
(
√
w/N
P
) group operations per client, which is not a linear speedup.
Since we are using distinguished points one should be able to do better. But the kangaroo
method is not as straightforward to parallelise as the rho method (a good exercise is to stop
reading now and think about it for a few minutes). The solution is to use a herd of
N
P
/
2
tame kangaroos and a herd of
N
P
/
2 wild kangaroos. These are super-kangaroos in the
sense that they take much bigger jumps (roughly
N
P
/
2 times longer) than in the serial case.
The goal is to have a collision between one of the wild kangaroos and one of the tame
kangaroos. We imagine that both herds are setting traps, each trying to catch a kangaroo
from the other herd (regrettably, they may sometimes catch one of their own kind).
When a kangaroo lands on a distinguished point one continues the pseudorandom walk
(rather than restarting the walk at a new randomly chosen position). In other words, the
herds march ever onwards with an occasional individual hitting a distinguished point and
sending information back to the server. See Figure
14.2
for a picture of the herds in
action.
There are two versions of the distributed algorithm, one by van Oorschot and
Wiener [
423
] and another by Pollard [
438
]. The difference is how they handle the pos-
sibility of collisions between kangaroos of the same herd. The former has a mechanism to
deal with this, which we will explain later. The latter paper elegantly ensures that there will
not be collisions between individuals of the same herd.
