Cryptography Reference
In-Depth Information
one can solve this problem using the rho algorithm, but if w is much smaller than the order
of g then this will not necessarily be optimal.
The kangaroo method was originally proposed by Pollard [ 437 ]. Van Oorschot and
Wiener [ 423 ] greatly improved it by using distinguished points. We present the improved
version in this section.
For simplicity, compute h =
hg b . Then h
g x (mod p ) where 0
x<w . Hence,
there is no loss of generality by assuming that b
=
0. Thus, from now on our problem is:
g a and 0
given g,h,w , find a such that h
a<w .
As with the rho method, the kangaroo method relies on a deterministic pseudorandom
walk. The steps in the walk are pictured as the “jumps” of the kangaroo, and the group
elements visited are the kangaroo's “footprints”. The idea, as explained by Pollard, is
to “catch a wild kangaroo using a tame kangaroo”. The “tame kangaroo” is a sequence
x i =
=
hg b j where b j is
known. Eventually, a footprint of the tame kangaroo will be the same as a footprint of the
wild kangaroo (this is called the “collision”). After this point, the tame and wild footprints
are the same. 8 The tame kangaroo lays “traps” at regular intervals (i.e., at distinguished
points) and, eventually, the wild kangaroo falls in to one of the traps. 9 More precisely, at
the first distinguished point after the collision, one finds a i and b j such that g a i
g a i
where a i is known. The “wild kangaroo” is a sequence y j =
hg b j and
=
g a i b j .
There are two main differences between the kangaroo method and the rho algorithm.
the DLP is solved as h
=
Jumps are “small”. This is natural since we want to stay within (or, at least, not too far
outside) the interval.
When a kangaroo lands on a distinguished point one continues the pseudorandom walk
(rather than restarting the walk at a new randomly chosen position).
14.5.1 The pseudorandom walk
The pseudorandom walk for the kangaroo method has some significant differences to the
rho walk: steps in the walk correspond to known small increments in the exponent (in other
words, kangaroos make small jumps of known distance in the exponent). We therefore do not
include the squaring operation x i + 1 =
x i (as the jumps would be too big) or multiplication
by h (we would not know the length of the jump in the exponent). We now describe the
walk precisely.
As in Section 14.2.1 , we use a function S : G
→{
0 ,...,n S
1
}
which partitions G into
S i ={
=
}
sets
g
G : S ( g )
i
of roughly similar size.
8
A collision between two different walks can be drawn in the shape of the letter λ . Hence, Pollard also suggested this be called
the “lambda method”. However, other algorithms (such as the distributed rho method) have collisions between different walks,
so this naming is ambiguous. The name “kangaroo method” emphasises the fact that the jumps are small. Hence, as encouraged
by Pollard, we do not use the name “lambda method” in this topic.
9
Actually, the wild kangaroo can be in front of the tame kangaroo, in which case it is better to think of each kangaroo trying to
catch the other.
Search WWH ::




Custom Search