Cryptography Reference
In-Depth Information
Algorithm 19
The distributed kangaroo algorithm (van Oorschot and Wiener version):
client side
INPUT: (
x
1
,a
1
,
type
)
, function
walk
1:
while
terminate signal not received
do
2:
∈
G
× Z
/r
Z
(
x
1
,a
1
)
=
walk
(
x
1
,a
1
)
if
x
1
∈
D
then
3:
Send (
x
1
,a
1
,
type
)toserver
4:
if
Receive jump instruction
then
5:
Choose random 1
<u<
2
m
(where
m
is the mean step size)
6:
Set
a
1
=
a
1
+
u
,
x
1
=
x
1
g
u
7:
8:
end if
9:
end if
10:
end while
We now consider the footsteps of the rear herd in the region already visited by the front
herd of kangaroos. Assuming the
N
P
/
2 kangaroos of the front herd are independent, the
region already covered by these kangaroos is expected to have
N
P
/
2 footprints in each
interval of length
m
. Hence, under our heuristic assumptions, the probability that a random
footprint of one of the rear kangaroos lands on a footprint of one of the front kangaroos is
N
P
/
(2
m
). Since there are
N
P
/
2 rear kangaroos, all mutually independent, the probability
of one of the rear kangaroos landing on a tame footprint is
N
P
/
(4
m
). By the heuristic
assumption the expected number of footprints to be made before a collision occurs is
4
m/N
P
.
Finally, the collision will not be detected until a distinguished point is visited. Hence,
one expects a further 1
/θ
steps to be made.
The expected number of group operations made by each client in the average case is
therefore
w/
(4
m
)
4
m/N
P
+
+
1
/θ
. Ignoring the 1
/θ
term, this expression is minimised by
N
P
√
w/
4. The result follows.
taking
m
=
The remarks made in Section
14.3.1
about parallelisation (for example, Exercise
14.3.3
)
apply equally for the distributed kangaroo algorithm.
Exercise 14.6.3
The above analysis is optimised for the average-case running time. Deter-
mine the mean step size to optimise the wors
t-
case expected running time. Show that the
heuristic optimal running time is (3
o
(1))
√
w/N
P
group operations.
+
Exercise 14.6.4
Give distributed versions of the three-kangaroo and four-kangaroo algo-
rithms of Section
14.5.5
.
14.6.2 Pollard version
Pollard's version reduces the computation to essentially a collection of serial versions, but
in a clever way so that a linear speed-up is still obtained. One merit of this approach is that
