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

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

3.Known special attacks

We now consider attacks which apply to certain special classes of elliptic curves.

3.1.Equivalence classes.The use of equivalence classes to accelerate the Pollard methods wasfirst noticed by Gallant,Lambert and Vanstone[13]and Wiener and Zuccherato[43].

The principle behind the Pollard methods is that two random walks on a set of size l are likely to have a collision after approximately πl/2steps.Hence,if the size of the set can be reduced then the time required tofind collisions is also reduced.The principle behind the equivalence classes method is that,if there is a convenient equivalence relation on the set,then one can consider a random walk on the set of equivalence classes rather than the whole set.The only difficulty is that it must be easy to construct a random walk which is well-defined on equivalence classes.

A basic example which works for all elliptic curves is the following,which is based on inverses of a point.If P=(x,y)then−P is either(x,−y)in the odd case or(x,y+x)in the even case.In both cases it is computationally trivial to pass from P to−P(this is quite unlike the case offinitefields,where computing g−1from g is a complicated arithmetic operation).Define the equivalence relation P∼Q if Q=±P and consider the set of equivalence classes S=E(K)/∼.Note that#S≈#E(K)/2.

We want to define a random walk on the set S as we did in Section2.4but we have

to take care of the following:when we have P i being mapped to P i+1=P i+M h(P

i )

we must also have−P i mapped to±P i+1.This means that we must be very careful in evaluating the function h which determines the choice of multiplier.A way to define h on equivalence classes is to impose an ordering on thefinitefield elements.Then,for a given point P=(x,y)one may compute−P=(x,y )and then determine whether y≤y or not.Finally one defines the function h as before, but in terms of the uniquely specified point whose y-coordinate has the minimal value.

Now that h is uniquely defined on equivalence classes it remains to construct the random walk on equivalence classes.One way to do this is to define P i+1=

P i+M h(P

i )

if y is the minimal value,and to define P i+1=P i−M h(P

i

)

if y is

the minimum value.The corresponding values of s i and t i are updated as s i+1=

s i±a h(P

i )

accordingly.Note that if P i=(x,y)is the point with minimal y-

coordinate and−P i=(x,y )is the other point,then−P i+1=−(P i+M h(P

i )

)=

(−P i)−M h(−P

i )

which shows that the map is well-defined on equivalence classes.

Note that,in the notation of Section2.4,we have P i=[s i]P+[t i]Q and−P i=

[−s i]P+[−t i]Q.

Finally,we must consider the distinguished points.We can use the same def-

inition as before for distinguished points of E(K)and now define an equivalence

{±P}of S to be distinguished if either P or−P is distinguished.The central server stores distinguished points and the values s i,t i.When two processorsfind

the same distinguished equivalence class then we have

[s i]P+[t i]Q=±([s j]P+[t j]Q).

The discrete logarithm problem can then be solved with high probability.

This trick of using the equivalence classes{±P}can be applied to all elliptic

curves.The way to abstract this method is to think of the process±as being an