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 PROBLEM19 dimension p.The difficulty of the ECDLP depends on whether there exist curves of‘small’genus on this variety.Unless the abelian variety A has some very special properties then it seems to be very unlikely that A always has such curves in it. Indeed,the analysis of the GHS attack has reinforced the opinions of researchers that Weil descent is only applicable to a very small proportion of elliptic curves if the extensionfield is chosen to have prime degree p.

Note that almost all research on Weil descent has been performed in character-istic2,since this is the most important case.In fact,the ideas are easily applied to otherfinitefields F p n where p is odd and n>1.The results in these cases are not as strong as in the case of characteristic two,but we still recommend against using such systems if n has a factor which lies between4and10.

Implication8.The GHS and the Weil Descent methodology imply that one should take q=2p,where p is a prime in the even characteristic case.

We emphasise that the Weil descent methods do not apply to elliptic curves over primefields F p.

3.6.Specialfinitefields.There are implementation advantages from using ellip-tic curves overfinitefields F p where p is of a special form such as a generalised Mersenne number.These are primes of the form

p=f(2w)

where w is a multiple of the word size and f is a sparse polynomial with coefficients drawn from{−1,0,1}.As an example we have

p=2192−264−1=f(264)

where

f=x3−x−1.

We are not aware of any security risk associated with using these particularfinite fields.There are no results in the theory of elliptic curve cryptography which suggest that some primefields are more or less secure than others.

4.Koblitz curves versus general curves

The term‘Koblitz curves’originally referred to certain elliptic curves over the field F2.Koblitz[22]pointed out that there are two advantages to performing elliptic curve cryptography in the group E(F2n)when E is defined over F2,namely:

(1)It is easy to compute the group order#E(F2n).

(2)The arithmetic can been made faster by using Frobenius expansions.

Thefirst advantage above is no longer important as there are now extremely efficient algorithms for counting points on elliptic curves overfields of small characteristic [17].The second advantage is still of interest,as it can lead to cryptographic systems with improved performance.Hence Koblitz curves have remained very popular for implementations of elliptic curve cryptography.

Since we always want curves whose group order is divisible by a large prime it follows that we must take the extension degree n to be prime(otherwise the curve have large subgroups corresponding to the subfields of F2n and so the group order has various significant factors).Hence,Koblitz curves over F2are not generally at risk from the Weil descent attack.