Cryptography Reference
In-Depth Information
14.5.5 Using inversion
Galbraith, Ruprai and Pollard [
209
] showed that one can improve the kangaroo method by
exploiting inversion in the group.
10
Suppose one is given
g,h,w
and told that
h
g
a
with
=
0
a<w
. We also require that the order
r
of
g
is odd (this will always be the case, due
to the Pohlig-Hellman algorithm). Suppose, for simplicity, that
w
is even. Replacing
h
by
hg
−
w/
2
we have
h
≤
g
a
with
a<w/
2. One can perform a version of the kangaroo
method with three kangaroos: one tame kangaroo starting from
g
u
for an appropriate value
of
u
and two wild kangaroos starting from
h
and
h
−
1
respectively.
The algorithm uses the usual kangaroo walk (with mean step size to be determined
later) to generate three sequences (
x
i
,a
i
)
,
(
y
i
,b
i
)
,
(
z
i
,c
i
) such that
x
i
=
=
−
w/
2
≤
g
a
i
,
y
i
=
hg
b
i
and
z
i
=
h
−
1
g
c
i
. The crucial observation is that a collision between any two sequences leads
to a solution to the DLP. For example, if
x
i
=
g
a
i
−
b
j
y
j
then
h
=
and if
y
i
=
z
j
then
g
(
c
j
−
b
i
)2
−
1
(mod
r
)
. The algorithm uses
distinguished points to detect a collison. We call this the
three-kangaroo algorithm
.
h
−
1
g
c
j
and so, since
g
has odd order
r
,
h
hg
b
i
=
=
Exercise 14.5.11
Write down pseudocode for the three-kangaroo algorithm using distin-
guished points.
We now give a brief heuristic analysis of the three-kangaroo algorithm. Without loss
of generality, we assume 0
w/
2 (taking negative
a
simply swaps
h
and
h
−
1
,so
does not affect the running time). The distance between the starting points of the tame
and wild kangaroos is 2
a
. The distance between the starting points of the tame and right-
most wild kangaroo is
≤
≤
a
. The extreme cases (in the sense that the closest pair of
kangaroos are as far apart as possible) are when 2
a
|
a
−
u
|
=
u
−
a
or when
a
=
w/
2. Making
all these cases equal leads to the equation 2
a
=
u
−
a
=
w/
2
−
u
. Calling this distance
l
it follows that
w/
2
3
w/
10. The average distance between the closest
pair of kangaroos is then
w/
10 and the closest pair of kangaroos can be thought of as
performing the standard kangaroo method in an interval of length 2
w/
5. Following the
analysis
of the
stan
dard k
angaroo
me
thod it is natural to take the mean step size to be
m
=
5
l/
2 and
u
=
2
2
w/
5
0
.
316
√
w
. The average-case expected n
umbe
r of group
op
er-
ations (only considering the closest pair of kangaroos) would be
=
√
w/
10
1
=
≈
2
2
2
w/
5
1
.
897
√
w
.A
more careful analysis takes into account the possibility of collisions between any pair of kan-
garoos. We re
fe
r to [
209
] for the details and merely remark that the correct mean step size is
m
3
≈
0
.
37
5
√
w
and the average-case expected number of group operations is approximately
1
.
818
√
w
.
≈
Exercise 14.5.12
The distance between
a
and
a
is even, so a natural trick is to use jumps
of even length. Since we do not know whether
a
is even or odd, if this is done we do not
know whether to start the tame kangaroo at
g
u
or
g
u
+
1
. However, one can consider a variant
of the algorithm with two wild kangaroos (one starting from
h
and one from
h
−
1
) and two
tame kangaroos (one starting from
g
u
and one from
g
u
+
1
) and with jumps of even length.
−
10
This research actually grew out of writing this chapter. Sometimes it pays to work slowly.
