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

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

1.Introduction

The Elliptic Curve Discrete Logarithm Problem(ECDLP)is the foundation of a number of cryptographic protocols,for example EC-DSA,EC-DH,EC-MQV, EC-IES etc.In this report we discuss the current state of knowledge about the difficulty of the ECDLP.Before doing so we set up some notation which will be used throughout.

Let K=F q denote afinitefield.In practical systems one always either chooses q to be a large prime or one chooses q to be a power of two,these correspond to the cases of odd and even characteristic respectively.An elliptic curve over K is usually given in one of two forms

E:Y2=X3+aX+b

in the odd case,or

E:Y2+XY=X3+aX2+b

in the even case.In both cases we assume a,b∈K are chosen to make the curve non-singular.

The set of points on an elliptic curve E over K,including the point at infinity which we write as O E,forms afinite abelian group denoted by E(K).We write the group operation on points of E(K)additively.For positive integers n we write

.

[n]P=P+P+···+P

n times

We sometimes also write this as nP.This is extended to all integers n∈Z using the inverse−P of a point.

We write the order of this group as

#E(K)=N.

We will always assume(see Section2.2for the reason)that N=h·l where l is a large prime number and h is small and called the cofactor.

Let P=(x,y)be a point on an elliptic curve E over K.We write

P ={[n]P:n∈Z}.

This is the subgroup of E(K)generated by the point P.The main problem which motivates elliptic curve cryptography is the following.

Elliptic Curve Discrete Logarithm Problem(ECDLP):Given P,Q∈E(K)find the value ofλ,if it exists,such that

Q=[λ]P.

For suitably chosenfields,curves and points this problem is believed to be com-putationally infeasible to solve.

Most cryptographic protocols in ECC actually rely for their security on weaker problems such as the elliptic curve Diffie-Hellman problem(EC-DHP)or the elliptic curve Decision Diffie-Hellman problem(EC-DDH).The cryptographic technique which we have been asked to study is the ECDLP,and so it will be the main focus of the present report.In order to accurately determine the security of cryptographic systems it is essential to also study the EC-DHP and EC-DDH.We recommend that the CRYPTREC organisation make further studies on these problems.In most