Cryptography Reference
In-Depth Information
the analysis of the serial kangaroo algorithm can be applied; we no longer need the strong
heuristic assumption that kangaroos in the same herd are mutually independent.
Let N P be the number of processors and suppose we can write N P =
U
+
V where
gcd( U,V )
N P / 2. The number of tame kangaroos is U and the number of
wild kangaroos is V . The (super) kangaroos perfor m t he usual pseudorandom walk with
steps
=
1 and U,V
N P w/ 4 (this is UV times the mean step
size for solving the DLP in an interval of length w/UV
{
UVu 0 ,...,UVu n 1 }
having mean m
4 w/N P ). As usual, we choose
2 j or else random values between 0 and 2 m/UV .
The U tame kangaroos start at
either u j
g w/ 2 + iV
i<U .The V wild kangaroos start at hg jU for 0
for 0
j<V . Each kangaroo then
uses the pseudorandom walk to generate a sequence of values ( x n ,a n ) where x n =
g a n or
x n =
hg a n . Whenever a distinguished point is hit the kangaroo sends data to the server and
continues the same walk.
Lemma 14.6.5 Suppose the walks do not cover the whole group, i.e. 0
a n <r. Then
there is no collision between two tame kangaroos or two wild kangaroos. There is a unique
pair of tame and wild kangaroos who can collide.
Proof Each element of the sequence generated by the i th tame kangaroo is of the form
g w/ 2 + iV + lUV
for some l
∈ Z
. To have a collision between two different tame kangaroos one would need
w/ 2
+
i 1 V
+
=
+
+
l 1 UV
w/ 2
i 2 V
l 2 UV
and reducing modulo U implies i 1
i 2 (mod U ) which is a contradiction. To summarise,
the values a n for the tame kangaroos all lie in disjoint equivalence classes modulo U .A
similar argument shows that wild kangaroos do not collide.
Finally,
) U 1
(mod V ) are the unique pair of indices such that the i th tame kangaroo and the j th wild
kangaroo can collide.
g a
a ) V 1
if h
=
then i
=
(
w/ 2
(mod U )
and j
=
( a
w/ 2
The analysis of the algorithm therefore reduces to the serial case, since we have one
tame kangaroo and one wild kangaroo who can collide. This makes the heuristic analysis
simple and immediate.
Theorem 14.6.6 Let the notation be as above. Assume Heuristic 14.5.4 and that all clients
are reliable and have the same computa tional p ower. Then th e average-case expected
running time for each client is (1
o (1)) w/UV
o (1)) w/N P group operations.
+
=
(2
+
Proof The action is now constrained to an equivalence class modulo UV , so the clients
behave like the serial kangaroo method in an interval of size w/UV (see Exercise 14.5.8
for reducing a DLP in a congruence class to a DLP in a smaller interval). The mean step
Search WWH ::




Custom Search