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 PROBLEM3

instances it is conjectured that all three problems are polynomial time equivalent. One should however be aware that there are some elliptic curves for which there is strong evidence for a separation between these problems(see Joux and Nguyen [20]).

There is a certain family of curves which occurs quite frequently in elliptic curve cryptography and they are called the‘Koblitz curves’.Originally this term was used for curves defined over a subfield k of K,where we consider the group of points over the largerfield for cryptographic purposes.The reason for considering these curves was that they possess an endomorphism structure which allows an efficient implementation of the various protocols.Nowadays,especially in standards such as SEC[1][2],the name‘Koblitz curve’is used for any elliptic curve which possesses a special endomorphism structure which enables efficient implementation.

There are two common classes of Koblitz curves:

•The classical case of curves over F2(sometimes called anomalous binary curves or ABC curves)which are given by

Y2+XY=X3+aX2+1

where a∈{0,1}.These curves are defined over F2but we work in the group of points defined over thefield F2n.

•The more recent case of Koblitz curves over a large primefield which have

a suitable endomorphism.

Further details of these cases are given in Section4.

2.Known generic attacks

In this section we consider a number of generic attacks against the ECDLP.The name‘generic’refers to the fact that such attacks will apply in any group and not just an elliptic curve group.What makes elliptic curves particularly attractive is that for well chosen parameter sets the following generic attacks are the best possible with current knowledge.

We always assume we have a discrete logarithm problem given by

Q=[λ]P,

where P and Q are given and the goal is tofindλ.

2.1.Exhaustive search.This is the most elementary attack.One simply com-putes

R=[µ]P

forµ=1,2,3,...,and checks whether R=Q.When equality is reached we concludeµ=λ.

This algorithm requires O(1)storage,but requires O(N)time in both the worst and average case.

2.2.Pohlig-Hellman.The discrete logarithm problem in a group G(for instance, G=E(K))is only as hard as the discrete logarithm problem in the largest subgroup of prime order in G.This observation is due to Pohlig and Hellman[31],and their method works in an arbitraryfinite abelian group.