Cryptography Reference
In-Depth Information
Algorithm 18
The distributed kangaroo algorithm (van Oorschot and Wiener version):
server side
INPUT:
g,h
G
, interval length
w
, number of clients
N
P
OUTPUT:
a
such that
h
∈
g
a
1:
Choose
n
S
, a random function
S
:
G
=
N
P
√
w/
4, jumps
→{
0
,...,n
S
−
1
}
,
m
=
{
u
0
,...,u
n
S
−
1
}
with mean
m
, spacing
s
=
2:
for
i
1to
N
P
/
2
do
Start
N
P
/
2 tame kangaroo clients
Set
a
i
=
+
is
4:
Initiate client on (
g
a
i
,a
i
,
'tame') with function
walk
5:
end for
6:
for
j
w/
2
3:
=
1to
N
P
/
2
do
Start
N
P
/
2 wild kangaroo clients
js
8:
Initiate client on (
hg
a
j
,a
j
,
'wild') with function
walk
9:
end for
10:
Initialise an easily sorted structure
L
(sorted list, binary tree etc) to be empty
11:
while
DLP not solved
do
12:
Set
a
j
=
7:
Receive triples (
x
i
,a
i
,
type
i
) from clients and insert into
L
if
first coordinate of new triple (
x,a
2
,
type
2
) matches existing triple (
x,a
1
,
type
1
)
then
13:
if
type
2
=
type
1
then
14:
Send message to the sender of (
x,a
2
,
type
2
) to take a random jump
15:
else
16:
Send terminate signal to all clients
17:
if
type
1
=
'tame'
then
18:
return
(
a
1
−
a
2
)(mod
r
)
19:
else
20:
return
(
a
2
−
a
1
)(mod
r
)
21:
22:
end if
23:
end if
24:
end if
25:
end while
Theorem 14.6.2
Let N
P
be the number of clients (fixed, independent of w). Assume
Heuristic
14.6.1
and that all clients are reliable and have the same computing power. The
average-case expected number of gro
up
operations performed by the distributed kangaroo
method for each client is
(2
o
(1))
√
w/N
P
.
+
Proof
Since we do not know where the wild kangaroo is, we speak of the front herd and
the rear herd. The distance (in the exponent) between the front herd and the rear herd is, on
average,
w/
4. So it takes
w/
(4
m
) steps for the rear herd to reach the starting point of the
front herd.
