Recent progress on the elliptic curve discrete logarithm problem (Q908041): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q61914006, #quickstatements; #temporary_batch_1707252663060 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q61914006 / rank | |||
Normal rank |
Revision as of 00:04, 7 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recent progress on the elliptic curve discrete logarithm problem |
scientific article |
Statements
Recent progress on the elliptic curve discrete logarithm problem (English)
0 references
2 February 2016
0 references
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''.
0 references
discrete logarithm problem (DLP)
0 references
elliptic curve discrete logarithm problem (ECDLP)
0 references
summation polynomials
0 references
Pollard rho
0 references
index-calculus
0 references