Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields

Christophe Petit; Michiel Kosters; Ange Messeng

doi:10.1007/978-3-662-49387-8_1

Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields

Christophe Petit
, Michiel Kosters
, Ange Messeng

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Citations (Scopus)

Abstract

The elliptic curve discrete logarithm problem is one of the most important problems in cryptography. In recent years, several index calculus algorithms have been introduced for elliptic curves defined over extension fields, but the most important curves in practice, defined over prime fields, have so far appeared immune to these attacks.

In this paper we formally generalize previous attacks from binary curves to prime curves. We study the efficiency of our algorithms with computer experiments and we discuss their current and potential impact on elliptic curve standards.

Our algorithms are only practical for small parameters at the moment and their asymptotic analysis is limited by our understanding of Gröbner basis algorithms. Nevertheless, they highlight a potential vulnerability on prime curves which our community needs to explore further.

Original language	English
Title of host publication	Public-Key Cryptography – PKC 2016
Subtitle of host publication	19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II
Editors	Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, Bo-Yin Yang
Publisher	Springer
Pages	3-18
ISBN (Electronic)	978-3-662-49387-8
ISBN (Print)	978-3-662-49386-1
DOIs	https://doi.org/10.1007/978-3-662-49387-8_1
Publication status	Published - 18 Feb 2016
Event	19th IACR International Conference on Practice and Theory in Public-Key Cryptography - Taipei, Taiwan, Province of China Duration: 6 Mar 2016 → 9 Mar 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9615
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th IACR International Conference on Practice and Theory in Public-Key Cryptography
Country/Territory	Taiwan, Province of China
City	Taipei
Period	6/03/16 → 9/03/16

Access to Document

10.1007/978-3-662-49387-8_1

http://link.springer.com/10.1007/978-3-662-49387-8_1

Cite this

Petit, C., Kosters, M., & Messeng, A. (2016). Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields. In C.-M. Cheng, K.-M. Chung, G. Persiano, & B.-Y. Yang (Eds.), Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II (pp. 3-18). (Lecture Notes in Computer Science; Vol. 9615). Springer. https://doi.org/10.1007/978-3-662-49387-8_1

Petit, Christophe ; Kosters, Michiel ; Messeng, Ange. / Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields. Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II. editor / Chen-Mou Cheng ; Kai-Min Chung ; Giuseppe Persiano ; Bo-Yin Yang. Springer, 2016. pp. 3-18 (Lecture Notes in Computer Science).

@inproceedings{30c3330c24b043b684da988cedfbbd86,

title = "Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields",

abstract = "The elliptic curve discrete logarithm problem is one of the most important problems in cryptography. In recent years, several index calculus algorithms have been introduced for elliptic curves defined over extension fields, but the most important curves in practice, defined over prime fields, have so far appeared immune to these attacks. In this paper we formally generalize previous attacks from binary curves to prime curves. We study the efficiency of our algorithms with computer experiments and we discuss their current and potential impact on elliptic curve standards. Our algorithms are only practical for small parameters at the moment and their asymptotic analysis is limited by our understanding of Gr{\"o}bner basis algorithms. Nevertheless, they highlight a potential vulnerability on prime curves which our community needs to explore further. ",

author = "Christophe Petit and Michiel Kosters and Ange Messeng",

year = "2016",

month = feb,

day = "18",

doi = "10.1007/978-3-662-49387-8\_1",

language = "English",

isbn = "978-3-662-49386-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "3--18",

editor = "Cheng, \{Chen-Mou \} and Kai-Min Chung and Giuseppe Persiano and Bo-Yin Yang",

booktitle = "Public-Key Cryptography – PKC 2016",

note = "19th IACR International Conference on Practice and Theory in Public-Key Cryptography ; Conference date: 06-03-2016 Through 09-03-2016",

}

Petit, C, Kosters, M & Messeng, A 2016, Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields. in C-M Cheng, K-M Chung, G Persiano & B-Y Yang (eds), Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9615, Springer, pp. 3-18, 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, Province of China, 6/03/16. https://doi.org/10.1007/978-3-662-49387-8_1

Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields. / Petit, Christophe; Kosters, Michiel; Messeng, Ange.
Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II. ed. / Chen-Mou Cheng; Kai-Min Chung; Giuseppe Persiano; Bo-Yin Yang. Springer, 2016. p. 3-18 (Lecture Notes in Computer Science; Vol. 9615).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields

AU - Petit, Christophe

AU - Kosters, Michiel

AU - Messeng, Ange

PY - 2016/2/18

Y1 - 2016/2/18

N2 - The elliptic curve discrete logarithm problem is one of the most important problems in cryptography. In recent years, several index calculus algorithms have been introduced for elliptic curves defined over extension fields, but the most important curves in practice, defined over prime fields, have so far appeared immune to these attacks. In this paper we formally generalize previous attacks from binary curves to prime curves. We study the efficiency of our algorithms with computer experiments and we discuss their current and potential impact on elliptic curve standards. Our algorithms are only practical for small parameters at the moment and their asymptotic analysis is limited by our understanding of Gröbner basis algorithms. Nevertheless, they highlight a potential vulnerability on prime curves which our community needs to explore further.

AB - The elliptic curve discrete logarithm problem is one of the most important problems in cryptography. In recent years, several index calculus algorithms have been introduced for elliptic curves defined over extension fields, but the most important curves in practice, defined over prime fields, have so far appeared immune to these attacks. In this paper we formally generalize previous attacks from binary curves to prime curves. We study the efficiency of our algorithms with computer experiments and we discuss their current and potential impact on elliptic curve standards. Our algorithms are only practical for small parameters at the moment and their asymptotic analysis is limited by our understanding of Gröbner basis algorithms. Nevertheless, they highlight a potential vulnerability on prime curves which our community needs to explore further.

U2 - 10.1007/978-3-662-49387-8_1

DO - 10.1007/978-3-662-49387-8_1

M3 - Conference contribution

SN - 978-3-662-49386-1

T3 - Lecture Notes in Computer Science

SP - 3

EP - 18

BT - Public-Key Cryptography – PKC 2016

A2 - Cheng, Chen-Mou

A2 - Chung, Kai-Min

A2 - Persiano, Giuseppe

A2 - Yang, Bo-Yin

PB - Springer

T2 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography

Y2 - 6 March 2016 through 9 March 2016

ER -

Petit C, Kosters M, Messeng A. Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields. In Cheng CM, Chung KM, Persiano G, Yang BY, editors, Public-Key Cryptography – PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II. Springer. 2016. p. 3-18. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-49387-8_1

Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this