Computing discrete logarithms in $GF(p^6)$

Laurent Grémy 1 Aurore Guillevic 1 François Morain 2 Emmanuel Thomé 1
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption
Inria Saclay - Ile de France
Abstract : The security of torus-based and pairing-based cryptography relies on the difficulty of computing discrete logarithms in small degree extensions of finite fields of large characteristic. It has already been shown that for degrees 2 and 3, the discrete logarithm problem is not as hard as once thought. We address the question of degree 6 and aim at providing real-life timings for such problems. We report on a record DL computation in a 132-bit subgroup of $GF(p^6)$ for a 22-decimal digit prime, with $p^6$ having 422 bits. The previous record was for a 79-bit subgroup in a 240-bit field. We used NFS-DL with a sieving phase over degree 2 polynomials, instead of the more classical degree 1 case. We show how to improve many parts of the NFS-DL algorithm to reach this target.
Type de document :
Communication dans un congrès
Carlisle Adams and Jan Camenisch. 24th Annual Conference on Selected Areas in Cryptography, Aug 2017, Ottawa, Canada. Springer, LNCS, 10719, pp.85-105, 2017, Selected Areas in Cryptography. 〈http://sacworkshop.org/SAC17/SAC2017.htm〉. 〈10.1007/978-3-319-72565-9_5〉
Liste complète des métadonnées

Littérature citée [49 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01624662
Contributeur : Laurent Grémy <>
Soumis le : jeudi 26 octobre 2017 - 16:03:48
Dernière modification le : jeudi 7 février 2019 - 15:43:04
Document(s) archivé(s) le : samedi 27 janvier 2018 - 14:01:54

Fichier

p6hd.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INSMI | INRIA | LORIA | LORIA-ALGO | UNIV-LORRAINE | INRIA2017 | UNIV-PARIS-SACLAY | GRID5000

Citation

Laurent Grémy, Aurore Guillevic, François Morain, Emmanuel Thomé. Computing discrete logarithms in $GF(p^6)$. Carlisle Adams and Jan Camenisch. 24th Annual Conference on Selected Areas in Cryptography, Aug 2017, Ottawa, Canada. Springer, LNCS, 10719, pp.85-105, 2017, Selected Areas in Cryptography. 〈http://sacworkshop.org/SAC17/SAC2017.htm〉. 〈10.1007/978-3-319-72565-9_5〉. 〈hal-01624662〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

568

Téléchargements de fichiers

242

Contact


archive-ouverte@inria.fr