Improving NFS for the discrete logarithm problem in non-prime finite fields

Razvan Barbulescu; Pierrick Gaudry; Aurore Guillevic; François Morain

doi:10.1007/978-3-662-46800-5_6

Improving NFS for the discrete logarithm problem in non-prime finite fields

Razvan Barbulescu
, Pierrick Gaudry
, Aurore Guillevic
, François Morain

INRIA Institut National de Recherche en Informatique et en Automatique
Laboratoire d'Informatique (LIX)
Centre national de la recherche scientifique
Nancy Université

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

49 Citations (Scopus)

Abstract

The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF(pⁿ) where n is a small integer greater than 1. Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good polynomials that define the extension fields used in NFS. We design two new methods for this task, modifying the asymptotic complexity and paving the way for record-breaking computations. We exemplify these results with the computation of discrete logarithms over a field GF(p²) whose cardinality is 180 digits (595 bits) long.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Elisabeth Oswald, Marc Fischlin
Publisher	Springer Verlag
Pages	129-155
Number of pages	27
ISBN (Print)	9783662467992
DOIs	https://doi.org/10.1007/978-3-662-46800-5_6
Publication status	Published - 1 Jan 2015
Event	34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015 - Sofia, Bulgaria Duration: 26 Apr 2015 → 30 Apr 2015

Publication series

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

Conference

Conference	34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015
Country/Territory	Bulgaria
City	Sofia
Period	26/04/15 → 30/04/15

Access to Document

10.1007/978-3-662-46800-5_6

Cite this

Barbulescu, R., Gaudry, P., Guillevic, A., & Morain, F. (2015). Improving NFS for the discrete logarithm problem in non-prime finite fields. In E. Oswald, & M. Fischlin (Eds.), Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 129-155). (Lecture Notes in Computer Science; Vol. 9056). Springer Verlag. https://doi.org/10.1007/978-3-662-46800-5_6

Barbulescu, Razvan ; Gaudry, Pierrick ; Guillevic, Aurore et al. / Improving NFS for the discrete logarithm problem in non-prime finite fields. Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Elisabeth Oswald ; Marc Fischlin. Springer Verlag, 2015. pp. 129-155 (Lecture Notes in Computer Science).

@inproceedings{9040db2df4e84c9aaabe9d6520795208,

title = "Improving NFS for the discrete logarithm problem in non-prime finite fields",

abstract = "The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF(pn) where n is a small integer greater than 1. Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good polynomials that define the extension fields used in NFS. We design two new methods for this task, modifying the asymptotic complexity and paving the way for record-breaking computations. We exemplify these results with the computation of discrete logarithms over a field GF(p2) whose cardinality is 180 digits (595 bits) long.",

author = "Razvan Barbulescu and Pierrick Gaudry and Aurore Guillevic and Fran{\c c}ois Morain",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2015.; 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015 ; Conference date: 26-04-2015 Through 30-04-2015",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-662-46800-5\_6",

language = "English",

isbn = "9783662467992",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "129--155",

editor = "Elisabeth Oswald and Marc Fischlin",

booktitle = "Advances in Cryptology {\textendash} EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

}

Barbulescu, R, Gaudry, P, Guillevic, A & Morain, F 2015, Improving NFS for the discrete logarithm problem in non-prime finite fields. in E Oswald & M Fischlin (eds), Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science, vol. 9056, Springer Verlag, pp. 129-155, 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015, Sofia, Bulgaria, 26/04/15. https://doi.org/10.1007/978-3-662-46800-5_6

Improving NFS for the discrete logarithm problem in non-prime finite fields. / Barbulescu, Razvan; Gaudry, Pierrick; Guillevic, Aurore et al.
Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Elisabeth Oswald; Marc Fischlin. Springer Verlag, 2015. p. 129-155 (Lecture Notes in Computer Science; Vol. 9056).

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

TY - GEN

T1 - Improving NFS for the discrete logarithm problem in non-prime finite fields

AU - Barbulescu, Razvan

AU - Gaudry, Pierrick

AU - Guillevic, Aurore

AU - Morain, François

PY - 2015/1/1

Y1 - 2015/1/1

N2 - The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF(pn) where n is a small integer greater than 1. Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good polynomials that define the extension fields used in NFS. We design two new methods for this task, modifying the asymptotic complexity and paving the way for record-breaking computations. We exemplify these results with the computation of discrete logarithms over a field GF(p2) whose cardinality is 180 digits (595 bits) long.

AB - The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF(pn) where n is a small integer greater than 1. Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good polynomials that define the extension fields used in NFS. We design two new methods for this task, modifying the asymptotic complexity and paving the way for record-breaking computations. We exemplify these results with the computation of discrete logarithms over a field GF(p2) whose cardinality is 180 digits (595 bits) long.

U2 - 10.1007/978-3-662-46800-5_6

DO - 10.1007/978-3-662-46800-5_6

M3 - Conference contribution

AN - SCOPUS:84942584809

SN - 9783662467992

T3 - Lecture Notes in Computer Science

SP - 129

EP - 155

BT - Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Oswald, Elisabeth

A2 - Fischlin, Marc

PB - Springer Verlag

T2 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015

Y2 - 26 April 2015 through 30 April 2015

ER -

Barbulescu R, Gaudry P, Guillevic A, Morain F. Improving NFS for the discrete logarithm problem in non-prime finite fields. In Oswald E, Fischlin M, editors, Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer Verlag. 2015. p. 129-155. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-46800-5_6

Improving NFS for the discrete logarithm problem in non-prime finite fields

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this