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

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

Hence we can obtain an equivalence relation as P∼Q if P=±φj(Q)for some j.The equivalence classes have size6.All the techniques developed above can be applied in this case and the algorithm runs faster by a factor of

√Similarly,the elliptic curve

E:y2=x3+x

(which has j-invariant j(E)=0)has the automorphism

(x,y)−→(−x,iy)

of order4,where i2=−1.This can also be used to speed up the Pollard methods by a factor of2.

With all of these methods there is a risk of getting trapped in small cycles.In practice these are easily eliminated and we refer to[13,43]for details.

The computational time of the equivalence classes method is the following:If the equivalence classes have size m and the group is of size l then the expected running time of the method is

c πl/2m

where the constant c depends on the cost of computing afixed representative for each equivalence class.Of course,from the point of view of computational complex-ity,the constant c is O(m)and so the equivalence classes method is asymptotically slower!But in practice it gives a very significant improvement to the running time, as the constant c is rather small.

We now discuss how this method effects the choice of parameters for elliptic curve cryptosystems.Suppose we want to develop a cryptosystem which requires a work effort(for a single processor)of280to be broken.Then we could take an elliptic curve over afinitefield which has a subgroup of prime order l where l>2160.Now suppose we would like to take advantage of the efficiency benefits enabled by the Frobenius endomorphism,and so we take an elliptic curve E over F2and consider the group E(F2m).One might expect that taking m=163gives the desired level of security.In fact,with m=163one obtains an elliptic curve with a subgroup of order l<2163(there is always some co-factor).The work effort to solve the ECDLP on such a curve using the Pollard method with equivalence classes is at most

c πl/2m<c π2163/(2·2·163)≤c281/10.2<c278.

In fact,to obtain280security it is necessary to take the extension degree m to be at least168.

Every elliptic curve over F q has some non-trivial endomorphisms.So why can’t they be used to improve the Pollard methods?The reason why they can’t be used is that it is not usually efficient tofind a canonical representative of an equivalence class.For instance,consider an elliptic curve E(F q)with l points and consider an integer n which is coprime to l.Inspired by the above methods we might impose the equivalence relation on E(F q)that P∼Q if and only if P=±[n]j Q for some j.The

first observation is that the powers n j may generate a large subgroup of Z∗

l and so

the equivalence classes may be very large.More importantly,to define the mapping h on equivalence classes it is necessary to have some canonical representative.The task of searching through the equivalence class is very expensive since each step is an elliptic curve point multiplication.In the notation above,the“constant”c is a significant multiple of m and so the complexity is not reduced.In general,the equivalence classes method is a slower algorithm than the usual Pollard method.