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 PROBLEM17 In[41]Smart examined the GHS attack for elliptic curves with respect to the field extension F2155/F231and concluded that such a technique was unlikely to work for any curve defined over F2155.Jacobson,Menezes and Stein[19]also examined thefield F2155,this time using the GHS attack down to the subfield F25.They concluded that such a strategy could be used in practice to attack around233 isomorphism classes of elliptic curves defined over F2155.Since there are about2156 isomorphism classes of elliptic curves defined over F2155,the probability offinding one where the GHS attack is applicable is negligible.Further analysis of the GHS attack has been given by Maurer,Menezes and Teske[26].

We now give some details of the GHS attack.

Let usfirst set up some notation.Throughout this section we let E denote an elliptic curve over thefield K=F q n where q=2r.Let k denote the subfield F q. To simplify the discussion,and since those cases are the most important,we always assume that r and n are odd.We also assume that n is a prime.We stress that it is easy to obtain analogous results in the more general case.

We assume the curve is given by an equation of the form

E:Y2+XY=X3+aX2+b where a∈{0,1},b∈K.

We may assume that a∈{0,1}since r and n are odd.We have points P,Q∈E(K) of large prime order l(we may assume that l≈q n)and we aim to solve the discrete logarithm problem.

Defineσ:K→K to be the q-power Frobenius automorphism,and letπ:K→K denote the absolute Frobenius automorphismπ:α→α2.Therefore,σ=πr.

Thefirst step is to construct the Weil restriction of scalars W E/k of E over k,this is an n-dimensional abelian variety over k with the property that W E/k(k)∼=E(K). The variety W E/k is then intersected with n−1carefully chosen hyperplanes so as to obtain a hyperelliptic curve C over thefield k.Let g denote the genus of C.

In addition,the GHS attack gives an explicit and efficient group homomorphism from E(K)to the Jacobian J C(k)of the curve C.Assuming some mild conditions, the Jacobian of C will contain a subgroup of order l and the image of the subgroup of order l in E(K)will be a non-trivial subgroup of order l in J C(k).

One can then translate the original ECDLP into a discrete logarithm problem on the Jacobian of the curve C over k=F q.The available algorithms have complexity depending on q g where g is the genus of the curve C.Hence the method is only successful when g is not too large.

One of the key results of[16]is the following.

Theorem2(Gaudry,Hess and Smart[16]).The genus of C is equal to either 2m−1or2m−1−1,where m is determined as follows.Let b i=σi(b),then m is

given by

m=m(b)=dim F

2 Span F2 (1,b1/20),...,(1,b1/2n−1) .

In particular we have1≤m≤n.If m is too small then the size of J C(k), which is≈q g,will be too small to contain a subgroup of size l.If m is too large then,although we can translate discrete logarithm problems to the hyperelliptic setting,the genus of the resulting curve is high and so the algorithms for solving the discrete logarithm problem are not effective.Hence,this case does not help us to solve the original ECDLP in practice.

Menezes and Qu proved the following theorem which characterises the smallest value of m>1and the elliptic curves which give rise to such m.