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

Razvan Barbulescu 1, 2, 3 Pierrick Gaudry 3 Aurore Guillevic 1, 2 François Morain 1, 2
1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption
Inria Saclay - Ile de France
3 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF($p^n$) 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 valuations 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^2$) whose cardinality is 180 digits (595 bits) long.
Keywords : discrete logarithm finite field record breakings Number Field Sieve
Type de document :
Communication dans un congrès
Marc Fischlin and Elisabeth Oswald. Eurocrypt 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2015, Sofia, Bulgaria. Lecture Notes in Computer Sciences, 9056, pp.129-155, 2015, Advances in Cryptology -- EUROCRYPT 2015. 〈https://www.cosic.esat.kuleuven.be/eurocrypt_2015〉. 〈10.1007/978-3-662-46800-5_6〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01112879
Contributeur : Aurore Guillevic <>
Soumis le : vendredi 3 juin 2016 - 02:27:01
Dernière modification le : jeudi 7 février 2019 - 15:43:17
Document(s) archivé(s) le : dimanche 4 septembre 2016 - 10:10:21

Fichiers

BGGM-Eurocrypt15.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

X | LIX | INRIA | UNIV-LORRAINE | X-LIX | PARISTECH | LORIA-ALGO | LORIA | UNIV-PARIS-SACLAY | X-DEP-INFO

Relations

Citation

Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, François Morain. Improving NFS for the discrete logarithm problem in non-prime finite fields. Marc Fischlin and Elisabeth Oswald. Eurocrypt 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2015, Sofia, Bulgaria. Lecture Notes in Computer Sciences, 9056, pp.129-155, 2015, Advances in Cryptology -- EUROCRYPT 2015. 〈https://www.cosic.esat.kuleuven.be/eurocrypt_2015〉. 〈10.1007/978-3-662-46800-5_6〉. 〈hal-01112879v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

735

Téléchargements de fichiers

497

Contact


archive-ouverte@inria.fr