Cryptography Reference
In-Depth Information
UV w/UV/ 2
N P w/ 4. Applying Theorem 14.5.5 gives the
size is therefore m
result.
14.6.3 Comparison of the two versions
Both versio ns of the distributed kangaroo method have the same heuristic running time of
(2
o (1)) w/N P group operations. 12 So which is to be preferred in practice? The answer
depends on the context of the computation. For genuine parallel computation in a closed
system (e.g., using special-purpose hardware) either could be used.
In distributed environments both methods have drawbacks. For example, the van
Oorschot-Wiener method needs a communication from server to client in response to
uploads of distinguished point information (the “take a random jump” instruction); though
Teske [ 544 ] has remarked that this can probably be ignored.
More significantly, both methods require knowing the number N P of processors at the
start of the computation, since this value is used to specify the mean step size. This causes
problems if a large number of new clients join the computation after it has begun.
With the van Oorschot and Wiener method, if further clients want to join the computation
after it has begun then they can be easily added (half the new clients tame and half wild) by
starting them at further shifts from the original starting points of the herds. With Pollard's
method it is less clear how to add new clients. Even worse, since only one pair of “lucky”
clients has the potential to solve the problem, if either of them crashes or withdraws from
the computation then the problem will not be solved. As mentioned in Section 14.4.3 , these
are serious issues which do arise in practice.
On the other hand, these issues can be resolved by over-estimating N P and by issuing
clients with fresh problem instances once they have produced sufficiently many distin-
guished points from their current instance. Note that this also requires communication from
server to client.
+
14.7 The Gaudry-Schost algorithm
Gaudry and Schost [ 228 ] give a different approach to solving discrete logarithm problems
using pseudorandom walks. As we see in Exercise 14.7.6 , this method is slower than the
rho method when applied to the whole group. However, the approach leads to low-storage
algorithms for the multi-dimensional discrete logarithm problems (see Definition 13.5.1 )
and the discrete logarithm problem in an interval using equivalence classes. This is inter-
esting since, for both problems, it is not known how to adapt the rho or kangaroo methods
to give a low-memory algorithm with the desired running time.
The basic idea of the Gaudry-Schost algorithm is as follows. One has pseudorandom
walks in two (or more) subsets of the group such that a collision between walks of different
12
Though the analysis by van Oorschot and Wiener needs the stronger assumption that the kangaroos in the same herd are
mutually independent.
Search WWH ::




Custom Search