Cryptography Reference
In-Depth Information
Figure 14.1 Kangaroo walk. Tame kangaroo walk pictured above the axis and wild kangaroo walk
pictured below. The dot indicates the first collision.
Since
√
w/
2
≈
3
.
64 it is appropriate to take
n
S
=
4 and choose steps
{
1
,
2
,
4
,
8
}
.The
F
263
are repre-
mean step size is 3
.
75. The function
S
(
x
)is
x
(mod 4) (where elements of
sented by integers in the set
{
1
,...,
262
}
).
=
(
g
26
,
26)
=
(26
,
26). The sequence of points
visited in the walk is listed below. A point is distinguished if its representation as an integer
is divisible by 3; the distinguished points are written in bold face in the table.
The tame kangaroo starts at (
x
1
,a
1
)
i
0
1
2
3
4
x
i
26
2
162
235
129
a
i
26
30
34
38
46
S
(
x
i
)
2
2
2
3
1
y
i
181
51
75
2
162
b
i
0
2
10
18
22
S
(
y
i
)
1
3
3
2
2
The collision is detected when the distinguished point 162 is visited twice. The solution
to the discrete logarithm problem is therefore 34
−
22
=
12.
=
Exercise 14.5.3
Using the same parameters as Example
14.5.2
,solvetheDLPfor
h
78.
14.5.3 Heuristic analysis of the kangaroo method
The analysis of the algorithm does not rely on the birthday paradox; instead, the mean
step size is the crucial quantity. We sketch the basic probabilistic argument now. A more
precise analysis is given in Section
14.5.6
. The following heuristic assumption seems to be
reasonable when
w
is sufficiently large,
n
S
>
log(
w
), distinguished points are sufficiently
common
an
d specified using a good hash function (and hence are well-distributed),
θ>
log(
w
)
/
√
w
and when the function
walk
is chosen at random.
Heuristic 14.5.4
1. Walks reach a distinguished point in significantly fewer than
√
w
steps (in other words,
there are no cycles in the walks and walks are not excessively longer than 1
/θ
).
2. The footprints of a kangaroo are uniformly distributed in the region over which it has
walked with, on average, one footprint in each interval of length
m
.
