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

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

Theorem3(Menezes and Qu[28]).Keeping the notation as above,and considering the GHS technique for Weil restriction of E from K down to k.Let n denote an odd prime,let t denote the multiplicative order of two modulo n and let s=(n−1)/t. Then

(1)The polynomial x n−1factors over F2as(x−1)f1f2···f s where the f i’s

are distinct irreducible polynomials of degree t.For1≤i≤s define

B i={b∈F q n:(σ−1)f i(σ)b=0}.

(2)For all1≤i≤s and all b∈B i the elliptic curves

Y2+XY=X3+b,

Y2+XY=X3+αX2+b

have m(b)≤t+1,whereαis afixed element of K of trace one.

(3)If m(b)=t+1then E must be one of the previous curves for some i and

some b∈B i.

(4)The cardinality of the set∪s i=1B i is qs(q t−1)+q.

In particular m(b)=t+1is the smallest attainable value of m(b),which is greater than one,for thefield F q n using the GHS technique for Weil restriction down to F q.

Menezes and Qu use the above theorem to show that if n is a prime in the range 160≤n≤600and if q=2then the GHS attack will be infeasible.These results are analysed in further detail by Jacobsson,Menezes and Stein[19]and Maurer, Menezes and Teske[26].

A new approach to Weil descent was very recently developed by Galbraith,Hess and Smart in[12].They show that one can sometimes apply the GHS attack to a curve which has a large value of m(b).The idea is tofind an isogenous curve E (K) which has a small value of m(b )and an isogeny

E(K)−→E (K).

The discrete logarithm problem in E(K)can then be mapped in to the discrete logarithm problem in E (K)and then this can be mapped using the GHS method to the discrete logarithm problem in the Jacobian of a hyperelliptic curve of low genus.Efficient methods tofind the isogenous curve and the isogeny are given in the paper[12],as well as a study as to how effective this extension to the GHS method is in practice.

While the work of Menezes and Qu shows that the GHS attack is not generally applicable to elliptic curve discrete logarithm problems over F2p where p is prime, it shows that there are some choices for p which are more dangerous than others (for instance,the case p=127).The danger of these special primes is not serious in practice,since all primes in the range160<p<600do not suffer from this risk.

One very important point is that the GHS attack is only one particular way to perform the general Weil descent strategy.One cannot deduce that a given instance of the elliptic curve discrete logarithm problem is hard simply by showing that the GHS attack cannot be applied.Hence,it is very important to think more generally about Weil descent as an attack on the ECDLP.

If we consider random elliptic curves overfinitefields of the form F2p then Weil descent can only be performed with respect to the degree p extension F2p/F2.The abelian variety A which arises from Weil descent therefore is defined over F2and has