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

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

function f which has divisor(f)=p(P)−p(O E).Defineϕ(P)to be the differential

ωP:=1d f.Then one can show that the mapϕ:P→ωP is a well-defined homomorphism intoΩ1(E).

To complete the description of(2)we need the homomorphismΩ1(E)→Z/p Z.

We may expand any differentialω∈Ω1(E)in terms of a uniformizer t at a point

P0.In other words,we may writeω= j a j t j dt.The Riemann-Roch theorem shows that a0cannot be zero sinceωis holomorphic(so it has no poles)and also

the divisor ofωhas degree2g−2=0(and so it cannot have any zeroes either).

The mapΩ1(E)→Z/p Z is simplyω= j a j t j dt→a0.That this is a homo-morphism follows from the fact that one may add the power series j a j t j in a termwise manner.

We now show how this map is used to solve the ECDLP on anomalous curves.

The attack is very simple,we merely evaluate the mapϕfrom the previous section

on both P and Q.Note that this map can be efficiently computed using a version

of the double-and-add method like that used to compute the Tate pairing.Since

this is a homomorphism into the additive group Z/p Z,the discrete logarithm is

simplyλ≡ϕ(Q)/ϕ(P)(mod p).This can be solved efficiently using the Euclidean

algorithm.

Implication7.In the case of large odd characteristic one should always have

l=q.

We emphasise that this test is trivial to perform and that the probability of a

random non-supersingular curve failing this test is negligible.

3.5.Weil descent.This method applies to elliptic curves overfield extensions of

the form F q n where q is a prime or prime power and where n>1.The principle

is to transform the ECDLP from E(F q n)to a discrete logarithm problem on the

Jacobian of a curve C over F q.Since subexponential algorithms exist for the discrete

logarithm problem in high genus curves,this gives a possible method of attack

against the ECDLP.

The technique of Weil descent to solve the elliptic curve discrete logarithm prob-

lem(ECDLP)wasfirst proposed by Frey[8].This strategy was detailed further by

Galbraith and Smart[11].These papers were rather general in their scope,but were

not detailed enough to give precise and efficient algorithms to solve the ECDLP for

specific curves.

The work of Gaudry,Hess and Smart[16]was less general than the earlier works

but gave much more powerful and efficient techniques.In particular,they gave

a very efficient algorithm to reduce the ECDLP to the discrete logarithm in a

Jacobian of a hyperelliptic curve over F q.We refer to the method of[16]as the

GHS attack.

Menezes and Qu[28]analysed the GHS attack in some detail and demonstrated

that it did not apply to the case when q=2and n is prime.Since this is the

common case in real world applications,the work of Menezes and Qu means that

the GHS attack does not apply to most deployed systems.However,there are a

fewfielded elliptic curve systems which use thefields F2155and F2185,in the IPSEC

standards.Hence there is considerable interest as to whether the GHS attack makes

all curves over thesefields vulnerable.