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

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

the double-and-add algorithm and evaluating all the intermediate functions at Q (see [9],[10]for details).

The value f (Q )lies in F q k and is only determined up to a multiple of an l th power.By raising it to the power (q k −1)/l we obtain a precise l th root of unity.One subtlety when implementing the Tate pairing is finding a divisor class Q with support disjoint from the partial terms in the addition chain for lP .In the elliptic curve case this is done by taking Q =(Q +S )−(S )where Q is the target point and where S is an arbitrary point (not necessarily of order l ).

We now recall how the Tate pairing is used to attack the ECDLP.The method proceeds as follows:

(1)Choose random points R ∈E (F q k )until P,R ∈(F ∗q k )l .

(2)Compute ζ1= P,R ,ζ2= Q,R ∈F ∗q k .

(3)Map the ζi to l th roots of unity (by raising to the power (q k −1)/l ).This step is actually optional since the linear algebra in the index calculus

method should be performed modulo l .

(4)Solve the discrete logarithm problem ζ2=ζλ1in the subgroup of order l of

the finite field F ∗q k using an index calculus method.

Note that the index calculus algorithms for solving the discrete logarithm prob-

lem in F ∗q k have subexponential complexity in terms of the field size q k (their per-

formance is comparable with integer factorisation algorithms).Since the original problem is in a group of size q it is necessary that the subexponential complexity in terms of q k be smaller than the complexity O (√q )of the Pollard methods.Hence,this strategy is only practical when k is relatively small.

It is known that supersingular curves are vulnerable to the Frey-R¨u ck attack (since the value k is always less than or equal to 6).There are also non-supersingular curves which are vulnerable to this attack (e.g.,curves of trace two over F q ).How-ever,if one chooses non-supersingular curves at random then the probability of finding a curve which is vulnerable to the Frey-R¨u ck attack is negligible (more precisely,the probability is O (1/√q )).Even more is true (as was shown by Bal-asubramanian and Koblitz [5]),if one chooses non-supersingular elliptic curves at random so that the number of points is a prime ,then the probability of finding a curve which is vulnerable to the Frey-R¨u ck attack is incredibly small (much smaller than 1/√q ).Implication 5.One should choose a curve such that

l |q k −1

for all “small”values of k ,e.g.,k ≤30.

This test will eliminate all supersingular curves and curves of trace two,plus a few others.

We emphasise that this test is trivial to perform and that the probability of a random non-supersingular curve failing this test is negligible.

3.3.Determining whether the ECDLP has a solution.The definition of the ECDLP often includes the task of deciding whether Q lies in the subgroup generated by P or not.