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 PROBLEM13 Implication4.Koblitz curves are slightly less secure then random curves over the samefield.

In particular,Koblitz curves over F2163only require a work effort of approximately 278to break the ECDLP,rather than approximately281.

3.2.Weil pairing and Tate pairing attacks.Menezes,Okamoto and Vanstone [27]were thefirst to show that the ECDLP may be transformed into a discrete logarithm problem in afinitefield.Their method used the Weil pairing.This method was generalised by Frey and R¨u ck[9]using the Tate pairing.We recall the Frey-R¨u ck attack here.

Let K=F q and let P and Q be points in E(K)of order l.Suppose that l is coprime to q(see Section3.4for the case where l|q).

Let k be a positive integer such that thefield F q k contains the l th roots of unity (in other words,l|(q k−1)and k is the order of q in Z∗l).Let G=E(F q k)and write G[l]for the subgroup of points of order l.Write lG={[l]P:P∈G}and write

G/lG for the quotient group.Similarly,write(F∗

q k )l={αl:α∈F∗

q k

}and write

F∗q k /(F∗

q k

)l for the quotient group.The groups G[l],G/lG and F∗

q k

/(F∗

q k

)l all have

exponent l(i.e.,they are a product of cyclic groups of order l).

The Tate pairing is a mapping

(1) ·,· :G[l]×G/lG→F∗

q k /(F∗

q k

)l.

The Tate pairing satisfies the following properties[9]:

(1)(Well-defined) 0,Q ∈(F∗

q k )l for all Q∈G and P,Q ∈(F∗

q k

)l for all

P∈G[l]and all Q∈lG.

(2)(Non-degeneracy)For each point P∈G[l]−{0}there is some point Q∈G

such that P,Q ∈(F∗

q k )l.

(3)(Bilinearity)For any integer n, [n]P,Q ≡ P,[n]Q ≡ P,Q n modulo l th

powers in F∗

q k

.

There are more properties,but these are the ones which are used for the attack.

The Weil pairing is a similar function,but in general there is no relationship between the Tate pairing and the Weil pairing,as they are defined on different sets.However,when E is an elliptic curve such that l2 #E(F q k)and P,Q are independent points in E(F q k)[l]then we have that the Weil pairing is

e l(P,Q)= P,Q / Q,P .

A consequence of the non-degeneracy property of the Weil pairing is that the Tate pairing is not symmetric.The Weil pairing requires working over thefield F q(E[l]) generated by the coordinates of all the l-division points.In general,one would expect the Weil pairing to require a largerfield than that used for the Tate pairing. One observation is that for elliptic curves thesefields are usually the same. Theorem1.(Koblitz)Let E be an elliptic curve over F q and let l be a prime dividing#E(F q).Suppose that l|(q−1).The E[l]⊂E(F q k)if and only if l|(q k−1).

The Tate pairing may be computed using the following process:Since[l]P=0 there is some function f on the curve E such that the divisor of the function f, which is denoted(f),is equal to l(P)−l(O E).Then P,Q =f(Q )where Q is a divisor in the same class as Q such that the support of Q is disjoint with the support of(f).This computation is easily and efficiently implemented in practice by using