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 PROBLEM11 easily computed endomorphism of the elliptic curve.Therefore,whenever we have an easily computed endomorphism of a curve then we are able to perform a similar method to speed up the Pollard methods.We now give further examples.

Consider the case of an elliptic curve E defined over F2but considered as a group over an extensionfield F2m.In this case there is the Frobenius endomorphism

π:(x,y)→(x2,y2)

on the curve E.On points P=(x,y)∈E(F2m)we haveπm(P)=(x2m,y2m)=P. In fact,there is an integerλsuch thatπ(P)=[λ]P for every point P=(x,y)∈E(F2m).Note that computingπ(P)from its definition as the Frobenius map is much faster than computing[λ]P using elliptic curve point multiplication algorithms,and this is the key to the speed-ups using Frobenius expansions.

We can define an equivalence relation P∼Q if P=±πn(Q)for some n.We want to construct a random walk on the set of equivalence classes S=E(F2m)/∼.

Given a point P i=[s i]P+[t i]Q we must obtain a new point in the random walk.We need a function h which maps all points in the same equivalence class to a number in{1,...,16}or so.This is done by searching through the equivalence class tofind a point which has a certain property(e.g.,the y-coordinated is minimal subject to an ordering condition).Once such a function h is provided there are two ways to proceed.

Thefirst approach makes use of the fact that we found a unique representative of the equivalence class while computing h.If the input point is P i=[s i]P+[t i]Q and if the unique representative is P i=(−1)jπk(P i)then we obtain the corresponding s i and t i via

s i=(−1)jλk s i(mod l)and t i=(−1)jλk t i(mod l).

One can then define a random walk using multipliers as before,and compute the s i+1and t i+1accordingly.

Another approach is to use a“next step”function which is well-defined on equiv-alence classes(instead of usingfixed multipliers M i).Such a process(which is used in[13])is to define the walks as

P i+1=P i+πh(P i)(P i)

so that s i+1=(1+λh(P i)s i)etc.

Either method can be used.In both cases we are using equivalence classes of size2m and so the expected running time of the algorithm is improved from approximately πl/2steps to approximately πl/(4m)steps.

The Frobenius endomorphism is particularly useful but it only occurs for elliptic curves defined over subfields.However,even with elliptic curves defined over prime fields there are sometimes endomorphisms available.An example of this occurs with the elliptic curve

E:y2=x3+A.

This elliptic curve has j-invariant j(E)=1728and it has the endomorphism

φ:(x,y)−→(βx,y)

whereβ3=1.As with the±and Frobenius maps,this is actually an automorphism (in other words,it has no kernel).Also,it is clear that this map has order three.