Abstract. This report discusses the elliptic curve discrete logarithm problem and the known methods to solve it. We consider the implications of these methods for choosing the domain parameters in elliptic curve based cryptographic schemes. We also study s

THE ELLIPTIC CUR VE DISCRETE LOGARITHM PROBLEM 7

The methods for reducing the space complexity all make use of random walks,and a number of techniques exist in the literature almost all of which are due to Pollard (such as the rho and lambda and kangaroo methods).

These algorithms were all developed for serial computers.In real life when one uses random walk based techniques to solve discrete logarithm problems one uses a parallel version due to van Oorschot and Wiener [30].The parallel methods are easily distributed over the internet.We now describe the parallel Pollard method as it is used in practice.

Suppose we are given the discrete logarithm problem

Q =[λ]P

in a subgroup G = P of an elliptic curve.The order of P is assumed to be a prime l .We first construct an easily computable function

h :G →{1,...,k },

where k is usually around 16.For example,such a function can be obtained by selecting a suitable window of 4bits in the binary representation of elements of G ,and mapping to an integer obtained from these bits in the natural way.

Then we define a set of “multipliers”M i ,these are produced by generating random integers a i ,b i ∈[0,...,l −1]and then setting

M i =[a i ]P +[b i ]Q.

(In fact,when working in a cyclic group such as P it is possible to set the b i =0as long as the t 0below are always taken to be distinct).

To start a random walk we pick random s 0,t 0∈[0,...,l −1]and compute

P 0=[s 0]P +[t 0]Q,

the random walk is then defined on the triples (P i ,s i ,t i )where

P i +1

=P i +M h (P i ),s i +1

=s i +a h (P i )(mod l ),t i +1=t i +b h (P i )(mod l ).

Hence,for every P i we record the values of s i and t i such that

P i =[s i ]P +[t i ]Q.

Suppose we have m processors,each processor starts a from a different starting position using the same process to determine the next element in the deterministic ‘random’walk.When two processors,or even the same processor,meet an element of the group that has been seen before then we obtain an equation

[s i ]P +[t i ]Q =[s j ]P +[t j ]Q,

from which we can solve for the discrete logarithm λwith high probability (the algorithm succeeds unless t i ≡t j (mod l )).It can be shown [30]that we expect that after roughly πl/2/m iterations of these parallel walks that we will find a collision and so solve the discrete logarithm problem.Hence the method requires O (√l/m )computation time.

However,as described above,each processor needs to return every element in its computed random walk to a central server who then stores all the computed elements.This is highly inefficient as the storage requirements will be very large,namely O (√l ).We can reduce the storage requirements to any value as follows.