Recent progress on the elliptic curve discrete logarithm problem (Q908041)

The ECDLP was proposed as an alternative cryptographic tool to the DLP on the multiplicative group of a finite field \(\mathbb{F}_q\), threatened by the index-calculus algorithm. The present paper gives a survey of the recent progress in the attacks to the ECDLP. Sections 2 and 3 summarize the basic notions on elliptic curves and the ECDLP and Section 4 and 5 the application to the ECDLP of the generic algorithms to solve the DLP (baby-step-giant-step, Pollard and kangaroo). Section 6 discusses the index-calculus algorithm in a generic cyclic group. Concerning the possibility of an efficient index-calculus for elliptic curves the paper concludes that ``elliptic curves over prime fields remain unaffected by index-calculus. This is no longer for some elliptic curves over extension fields''. Section 7 schematizes the application of the Weil descent method to the ECDLP on elliptic curves over an extension field \(\mathbb{F}_{q^n}\). The method, see Gaudry, Hess and Smart [\textit{P. Gaudry} et al., J. Cryptology 15, No. 1, 19--46 (2001; Zbl 0996.94036)], allows, in some few cases, to transfer the logarithm problem to the Jacobian of a curve over \(\mathbb{F}_q\), where the problem is easier. Section 8 and 9 deals with the application to the ECDLP of the so-called summation polynomials, see \textit{I. A. Semaev} [Cryptology ePrint Archive: Report 2015/310 (2015)]. Finally Section 10 discusses some open problems, in particular the possibility of a subexponential algorithm for the ECDLP in characteristic two. The authors say that ``we believed that elliptic curves over characteristic two fields \(\mathbb{F}_{2^n}\) of prime degree \(n\) are not threatened by such methods and are still safe for use''.