Recent progress on the elliptic curve discrete logarithm problem
type: Item
instance of: scholarly article
title: Recent progress on the elliptic curve discrete logarithm problem
zbMATH Open document ID: 1364.11164
author: Steven D. Galbraith
author: Pierrick Gaudry
published in: Designs, Codes and Cryptography
publication date: 2016-02-02T00:00:00Z
full work available at URL: DCC-survey.pdf
review text: 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''.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11G20
Mathematics Subject Classification ID: 14G15
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 14H52
zbMATH DE Number: 6538690
zbMATH Keywords: discrete logarithm problem (DLP)
zbMATH Keywords: elliptic curve discrete logarithm problem (ECDLP)
zbMATH Keywords: summation polynomials
zbMATH Keywords: Pollard rho
zbMATH Keywords: index-calculus
Wikidata QID: Q61914006
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
OpenAlex ID: W2218139189
cites work: Q4847910
cites work: Handbook of Elliptic and Hyperelliptic Curve Cryptography
cites work: Computing Small Discrete Logarithms Faster
cites work: Non-uniform Cracks in the Concrete: The Power of Free Precomputation
cites work: Q2949487
cites work: On the Correct Use of the Negation Map in the Pollard rho Method
cites work: Q4265362
cites work: Advances in Elliptic Curve Cryptography
cites work: Advances in Cryptology - EUROCRYPT 2004
cites work: Elliptic and Hyperelliptic Curves: A Practical Security Analysis
cites work: Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction
cites work: On the Use of the Negation Map in the Pollard Rho Method
cites work: Slope packings and coverings, and generic algorithms for the discrete logarithm problem
cites work: Hard Problems of Algebraic Geometry Codes
cites work: Security Analysis of the Strong Diffie-Hellman Problem
cites work: Discrete logarithm problems with auxiliary inputs
cites work: A Group Action on $${\mathbb Z}_p^{\times }$$ and the Generalized DLP with Auxiliary Inputs
cites work: Q4450525
cites work: Algorithmic Number Theory
cites work: On the discrete logarithm problem in class groups of curves
cites work: On the discrete logarithm problem in elliptic curves
cites work: On the discrete logarithm problem in elliptic curves. II
cites work: Elliptic codes over fields of characteristic 2
cites work: Efficient computation of zero-dimensional Gröbner bases by change of ordering
cites work: Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields
cites work: Sub-cubic change of ordering for Gröbner basis
cites work: Using symmetries in the index calculus for elliptic curves discrete logarithm
cites work: Symmetrized Summation Polynomials: Using Small Order Torsion Points to Speed Up Elliptic Curve Index Calculus
cites work: Multi-user Collisions: Applications to Discrete Logarithm, Even-Mansour and PRINCE
cites work: Q2712108
cites work: Q3421478
cites work: Constructing Isogenies between Elliptic Curves Over Finite Fields
cites work: Mathematics of public key cryptography.
cites work: Summation Polynomial Algorithms for Elliptic Curves in Characteristic Two
cites work: Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval
cites work: Q4945368
cites work: Q4737234
cites work: Computing discrete logarithms in an interval
cites work: Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm
cites work: Improving the parallelized Pollard lambda search on anomalous binary curves
cites work: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
cites work: Constructive and destructive facets of Weil descent on elliptic curves
cites work: A double large prime variation for small genus hyperelliptic index calculus
cites work: On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields
cites work: The Strong Law of Small Numbers
cites work: Q4826108
cites work: Generalising the GHS Attack on the Elliptic Curve Discrete Logarithm Problem
cites work: First fall degree and Weil descent
cites work: ANALYSIS OF POSSIBLE PRE-COMPUTATION AIDED DLP SOLVING ALGORITHMS
cites work: Global Duality, Signature Calculus and the Discrete Logarithm Problem
cites work: Improvement of Faugère et al.’s Method to Solve ECDLP
cites work: Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: On the last fall degree of zero-dimensional Weil descent systems

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Analysis of the Xedni calculus attack

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Algorithmic Cryptanalysis

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Cover and Decomposition Index Calculus on Elliptic Curves Made Practical

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Elliptic curve discrete logarithm problem over small degree extension fields

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Point Decomposition Problem in Binary Elliptic Curves

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Collision of Random Walks and a Refined Analysis of Attacks on the Discrete Logarithm Problem

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: A new approach to the discrete logarithm problem with auxiliary inputs

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Analysis on a generalized algorithm for the strong discrete logarithm problem with auxiliary inputs

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Another look at non-standard discrete log and Diffie-Hellman problems

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q3062282

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q2739459

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Deterministically generating Picard groups of hyperelliptic curves over finite fields

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Remarks on Cheon’s Algorithms for Pairing-Related Problems

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q4736434

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: A Generic Algorithm for Small Weight Discrete Logarithms in Composite Groups

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q2724449

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q5747103

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: How long does it take to catch a wild kangaroo?

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Decomposition Attack for the Jacobian of a Hyperelliptic Curve over an Extension Field

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Complexity of a determinate algorithm for the discrete logarithm

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Parallel collision search with cryptanalytic applications

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: On Polynomial Systems Arising from a Weil Descent

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Kangaroos, monopoly and discrete logarithms

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q3808150

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Solving a Discrete Logarithm Problem with Auxiliary Input on a 160-Bit Elliptic Curve

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: A simple method for obtaining relations among factor basis elements for special hyperelliptic curves

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Solving the Elliptic Curve Discrete Logarithm Problem Using Semaev Polynomials, Weil Descent and Gröbner Basis Methods – An Experimental Study

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q2935174

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Advances in Cryptology - ASIACRYPT 2003

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q4444944

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q5386130

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Solving the Discrete Logarithm of a 113-Bit Koblitz Curve with an FPGA Cluster

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Q4250816

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Generic Hardness of the Multiple Discrete Logarithm Problem

Recent progress on the elliptic curve discrete logarithm problem (cites work)
cites work: Speeding up elliptic curve discrete logarithm computations with point halving

Recent progress on the elliptic curve discrete logarithm problem (DBLP publication ID)
DBLP publication ID: journals/dcc/GalbraithG16

Recent progress on the elliptic curve discrete logarithm problem (DOI)
DOI: 10.1007/S10623-015-0146-7

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: On the discrete logarithm problem in elliptic curves
Similarity Score: 0.9393041
Recommender Run: Recommender Run 3

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: Несколько замечаний о задаче дискретного логарифмирования на эллиптических кривых
Similarity Score: 0.93890226
Recommender Run: Recommender Run 3

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: On the discrete logarithm problem for prime-field elliptic curves
Similarity Score: 0.9235878
Recommender Run: Recommender Run 3

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: On the discrete logarithm problem in elliptic curves. II
Similarity Score: 0.9192921
Recommender Run: Recommender Run 3

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: The Elliptic Curve Discrete Logarithm Problem and Equivalent Hard Problems for Elliptic Divisibility Sequences
Similarity Score: 0.9145906
Recommender Run: Recommender Run 3

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields
Similarity Score: 0.913424
Recommender Run: Recommender Run 3

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: Algorithms and Computation
Similarity Score: 0.9118803
Recommender Run: Recommender Run 3

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: Q4691420
Similarity Score: 0.9111598
Recommender Run: Recommender Run 3

Recent progress on the elliptic curve discrete logarithm problem (Recommended article)
Recommended article: Q2739457
Similarity Score: 0.9073556
Recommender Run: Recommender Run 3