Cryptography Reference
In-Depth Information
Figure 14.2 Distributed kangaroo walk (van Oorschot and Wiener version). The herd of tame kanga-
roos is pictured above the axis and the herd of wild kangaroos is pictured below. The dot marks the
collision.
14.6.1 Van Oorschot and Wiener version
We first present the algorithm of van Oorschot and Wiener. The herd of tame kangaroos
starts around the midpoint of the interval [0
,w
), and the kangaroos are spaced a (small)
distance
s
apart (as always, we describe kangaroos by their exponent). Similarly, the wild
kangaroos start near
a
log
g
(
h
), again spaced a dist
an
ce
s
apart. As we will explain later,
the mean step size of the jumps should be
m
=
N
P
√
w/
4.
Here
walk
(
x
i
,a
i
) is the function which returns
x
i
+
1
=
≈
x
i
g
S
(
x
i
)
and
a
i
+
1
=
a
i
+
u
S
(
x
i
)
.
Each client has a variable
type
which takes the value 'tame' or 'wild'.
If there is a collision between two kangaroos of the same herd then it will eventually be
detected when the second one lands on the same distinguished point as the first. In [
423
]
it is suggested that in this case the server should instruct the second kangaroo to take a
jump of random length so that it no longer follows the path of the front kangaroo. Note that
Teske [
544
] has shown that the expected number of collisions within the same herd is 2, so
this issue can probably be ignored in practice.
We now give a very brief heuristic analysis of the running time. The following assu
m
ption
seems to be reasonable when
w
is sufficiently large,
n
S
is sufficiently large, log(
w
)
/
√
w<θ
,
the set
of distinguished points is determi
ned b
y a good hash function, the number
N
P
of
clients is sufficiently small (e.g.,
N
P
<θ
√
πr/
2
/
log(
r
), see Exercise
14.3.3
), the spacing
s
is independent of the steps in the random walk and is sufficiently large and the function
walk
is chosen at random.
D
Heuristic 14.6.1
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. When two kangaroos with mean step size
m
walk over the same interval, the expected
number of group elements sampled before a collision is
m
.
3. Walks of kangaroos in the same herd are independent.
11
11
This assumption is very strong, and indeed is false in general (since there is a chance that walks collide). The assumption is
used for only two purposes. First, to “amplify” the second assumption in the heuristic from any pair of kangaroos to the level
of herds. Second, to allow us to ignore collisions between kangaroos in the same herd (Teske, in Section 7 of [
544
], has argued
that such collisions are rare). One could replace the assumption of independence by these two consequences.
