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 PROBLEM 15

In elliptic curve systems the point P usually has prime order l and the order N of the group E (K )is known to all users.

If N =l (i.e.,the subgroup generated by P is the full set of points on the curve)then it is sufficient simply to test whether the point Q lies on the curve (i.e.,whether it satisfies the curve equation).If so,then Q ∈ P .

More generally there is some non-trivial cofactor h =N/l .Usually l 2does not divide N (and this can be checked by all users of the system).This means that there is a unique subgroup of E (K )of order l and it is the subgroup generated by P .Hence,if Q has order l then Q must lie in P and the ECDLP does have some solution λ.Hence,the simplest test is to simply check whether [l ]Q =O E .

If the subgroup of points of order l in E (K )is not cyclic then l 2|N and the problem of checking whether the ECDLP has a solution is more difficult.Of course,this case usually does not arise in cryptography since,in that case,l ≤√N which means the system has poor efficiency.Nevertheless,the Weil pairing may be used to determine whether Q ∈ P or not (no field extension is necessary in this case,since the theory implies that l |(q −1)).Briefly,if the pairing of P and Q is one then Q ∈ P while if the pairing is not one then Q ∈ P and so the ECDLP does not have a solution.Implication 6.Deciding whether the ECDLP has a solution or not is rather easy in practice.

3.4.The anomalous curves attack.An elliptic curve E defined over a prime field F p is said to be anomalous if it has exactly p points.

In 1997several researchers independently announced related methods to reduce the discrete logarithm problem on an anomalous elliptic curve E/F p to the discrete logarithm problem in the additive group Z /p Z of the integers modulo p .Nigel Smart [40]posted an announcement on the internet briefly describing a method to solve this problem.At the same time a preprint appeared by Satoh and Araki [4],which used identical methods.It then became known that Semaev [35]had already submitted a paper on this topic,and that R¨u ck [33]had generalised this method to deal with Abelian varieties.In this section we will discuss the method of Semaev and R¨u ck,restricted to the case of elliptic curves.This method is computationally more efficient than the methods proposed by Smart and Satoh–Araki.The papers [4],

[40]give a very readable description of the alternative (p -adic logarithm)method.The paper by Voloch [42]puts the method into a more theoretical framework which demonstrates the analogy between these methods and the Tate pairing.

We note that anomalous curves E/F p are very rare.There is approximately 1/(4√p )chance of a random curve being anomalous.Also,this phenomenon has no impact for the case of elliptic curves over fields of small characteristic.

Suppose E/F p is an elliptic curve such that #E (F p )=p .In this section we will describe the mapping

(2)E [p ]−→Z /p Z

which is the key element of the attack on anomalous elliptic curves.

We will describe the map (2)in two stages.

The first stage is a mapping described by Serre from E [p ]into Ω1(E )(the space of holomorphic differentials on E ).Given P ∈E [p ]we know that there is some