EVALUATION REPORT FOR CRYPTREC SECURITY LEVEL OF CRYPTOGRAPH

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

EV ALUATION REPORT FOR CRYPTREC:

SECURITY LEVEL OF CRYPTOGRAPHY–ECDLP

MATHEMATICAL PROBLEM

S.D.GALBRAITH AND N.P.SMART

Abstract.This report discusses the elliptic curve discrete logarithm prob-

lem and the known methods to solve it.We consider the implications of these

methods for choosing the domain parameters in elliptic curve based crypto-

graphic schemes.We also study special classes of elliptic curves.In particular,

we discuss the security of Koblitz curves.

Contents

1.Introduction2

2.Known generic attacks3 2.1.Exhaustive search3 2.2.Pohlig-Hellman3 2.

3.Baby-Step/Giant-Step5 2.

4.Pollard methods6

2.5.Practical considerations8

3.Known special attacks10 3.1.Equivalence classes10 3.2.Weil pairing and Tate pairing attacks13 3.3.Determining whether the ECDLP has a solution14 3.

4.The anomalous curves attack15 3.

5.Weil descent16

3.6.Specialfinitefields19

4.Koblitz curves versus general curves19 4.1.Koblitz curves in characteristic220

4.2.Koblitz curves in characteristic p21

5.Possible special attacks21 5.1.Endomorphisms and complex multiplication22 5.2.Imagined attacks23 5.3.Koblitz curves revisited23

5.4.Trace three curves23

6.Conclusion23 References24

1