Cryptography Reference
In-Depth Information
3. The footsteps of tame and wild kangaroos are independent of one another before the
time when the walks collide.
Theorem 14.5.5
Let the notation be as above and assume Heuristic
14.5.4
. Then the
kangaroo al
go
rithm with distinguished points has average case expected running time of
(2
o
(1))
√
w group operations. The probability the algorithm fails is negligible.
+
Proof
We do not know whether the discrete logarithm of
h
is greater or less than
w/
2. So,
rather than speaking of “tame” and “wild” kangaroos we will speak of the “front” and “rear”
kangaroos. Since one kangaroo starts in the middle of the interval the distance between the
starting point of the rear kangaroo and the starting point of the front kangaroo is between
0 and
w/
2 and is, on average,
w/
4. Hence, on average,
w/
(4
m
) jumps are required for the
rear kangaro to pass the starting point of the front kangaroo.
After this point, the rear kangaroo is travelling over a region that has already been jumped
over by the front kangaroo. By our heuristic assumption, the footprints of the tame kangaroo
are uniformly distributed over the region with, on average, one footprint in each interval of
length
m
. Also, the footprints of the wild kangaroo are independent, and with one footprint
in each interval of length
m
. The probability, at each step, that the wild kangaroo does
not land on any of the footprints of the tame kangaroo is therefore heuristically 1
1
/m
.
By exactly the same arguments as Lemma
14.2.12
it follows that the expected number of
jumps until a collision is
m
.
Note that there is a miniscule possibility that the walks never meet (this does not require
working in an infinite group, it can even happen in a finite group if the “orbits” of the tame
and wild walks are disjoint subsets of the group). If this happens then the algorithm never
halts. Since the walk function is chosen at random the probability of this eventuality is
negligible. On the other hand, if the algorithm halts then its result is correct. Hence, this is
a Las Vegas algorithm.
The overall number of jumps made by the rear kangaroo until the first collision is
therefor
e,
on average,
w/
(4
m
)
−
+
m
. One can easily check that this is minimised by taking
=
√
w/
2. The kangaroo is also expected to perform a further 1
/θ
steps to the next
distinguished point. Since
th
ere are two kangaroos
t
he expected total number of group
operations performed is 2
√
w
m
o
(1))
√
w
.
+
=
+
2
/θ
(2
This result is proved by Montenegro and Tetali [
390
] under the assumption that
S
is a
random function and that the distinguished points are well-distributed. Pollard [
438
]shows
it is valid when the
o
(1) is replaced by
for some 0
<
0
.
06.
Note that the expected distance, on average, travelled by a kangaroo is
w/
4
≤
m
2
w/
2
steps. Hence, since the order of the group is greater than
w
, we do not expect any self-
collisions in the kangaroo walk.
We stress that, as with the rho method, the probability of success is considered over
the random choice of pseudorandom walk, not over the space of problem instances.
Exercise
14.5.6
considers a different way to optimise the expected running time.
+
=
