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

6S.D.GALBRAITH AND N.P.SMART

or,more efficiently,by the use of hash-tables.To compute and store the Baby-Steps clearly requires O ( √l )

time,and a similar amount of storage.We now compute the Giant-Steps.Let P =[ √ ]P and compute Q j =Q −[j ]P for 0≤j < √ .

We then try to find a match in the table of Baby-Steps,i.e.we try to find a value P i such that P i =Q j .If such a match occurs we have

λ0=i and λ1=j

since,in that case,

[i ]P =Q −[j √]P,

and so [i +j √l ]P =Q.

Notice that the time to compute the Giant-Steps is at most O ( √ ).

Hence,the overall time and space complexity of the Baby-Step/Giant-Step method is O (√l ).

This complexity is for both the worst and average cases of running the algorithm.

It is known (see Shoup [36])that the Baby-Step/Giant-Step method is the fastest possible method for solving the discrete logarithm problem in a ‘black box group’.Black box groups are a theoretical tool which allow the analysis of algorithms in an idealised setting.A black box group is a group modelled in such a way that the representations of field elements provides no structure.Of course in any particular group there may be a special purpose algorithm which works faster,but in general the Baby-Step/Giant-Step method is the best possible.

In conclusion,combining the Baby-Step/Giant-Step method with the Pohlig-Hellman algorithm,if we wish a discrete logarithm problem in a group G to be as difficult as a work effort of 280operations,then we need the group G to have a prime order subgroup of order at least 2160.Implication 2.This means that for elliptic curve cryptography we select a curve such that

#E (K )=N =h ·l

where

l >2160.

2.4.Pollard methods.The trouble with the Baby-Step/Giant-Step method is that,although its run time is bounded by O (√l ),it also requires O (√l )space.This space requirement makes the algorithm infeasible in practice.Hence,it is desirable to reduce the large space requirement while still obtaining a time complexity of O (√Pollard achieved this [32],but the method only has an expected running time rather than an absolute bound on the running time.The resulting algorithm is therefore of the “Las Vegas”type.