Cryptography Reference
In-Depth Information
u
j
≤
√
w
. Define
m
(
n
S
−
1
≤
≤
=
For 0
j<n
S
choose exponents 1
j
=
0
u
j
)
/n
S
to be the
≈
√
w/
2.
mean step size
. As explained below, we will take
m
2
j
as this minimises the chance that two
different short sequences of jumps add to the same value. This seems to give good results
in practice. An alternative is to choose
mo
st of the values
u
i
to be random and the last
Pollard [
437
,
438
] suggested taking
u
j
=
few to ensure that
m
is very close to
c
1
√
w
.
The pseudorandom walk is a sequence
x
0
,x
1
,...
of elements of
G
defined by an initial
value
x
0
(to be specified later) and the formula
x
i
+
1
=
x
i
g
S
(
x
i
)
.
The algorithm is not based on the birthday paradox, but instead on the following obser-
vations. Footprints are spaced, on average, distance
m
apart, so along a region traversed
by a kangaroo there is, on average, one footprint in any interval of length
m
.Now,ifa
second kangaroo jumps along the same region and if the jumps of the second kangaroo
are independent of the jumps from the first kangaroo, then the probability of a collision is
roughly 1
/m
. Hence, one expects a collision between the two walks after about
m
steps.
14.5.2 The kangaroo algorithm
We need to specify where to start the tame and wild kangaroos, and what the mean step
size should be. The wild kangaroo starts at
y
0
=
g
a
with 0
a<w
. To minimise the
distance between the tame and wild kangaroos at the start of the algorithm we start the
tame kangaroo at
x
0
=
h
=
≤
g
w/
2
, which is the middle of the interval. We take alternate jumps
and store the values (
x
i
,a
i
) and (
y
i
,b
i
) as above (i.e., so that
x
i
=
hg
b
i
).
Whenever
x
i
(respectively,
y
i
) is distinguished we store (
x
i
,a
i
) (respectively, (
y
i
,b
i
)) in an
easily searched structure. The storage can be reduced by using the ideas of Exercise
14.2.16
.
When the same distinguished point is visited twice then we have two entries (
x,a
) and
(
x,b
) in the structure and so either
hg
a
g
a
i
and
y
i
=
g
b
or
g
a
hg
b
. The ambiguity is resolved by
=
=
g
a
−
b
or not).
As
we
will explain in Section
14.5.3
, the optimal choice for the mean step size is
seeing which of
a
−
b
and
b
−
a
lies in the interval (or just testing if
h
=
=
√
w/
2.
m
Exercise 14.5.1
Write this algorithm in pseudocode.
We visualise the algorithm not in the group
G
but on a line representing exponents. The
tame kangaroo starts at
. The wild kangaroo starts somewhere in the interval [0
,w
).
Kangaroo jumps are small steps to the right. See Figure
14.1
for the picture.
w/
2
∈ F
263
Example 14.5.2
Let
g
=
3
which has prime order 131. Let
h
=
181
∈
g
and
g
a
with 0
suppose we are told that
h
=
≤
a<w
=
53. The kangaroo method can be used
in this case.
