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

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

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

Razvan Barbulescu ^{1, 2, 3} Pierrick Gaudry ³ 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

Document type :

Conference papers

Domain :

Computer Science [cs] / Cryptography and Security [cs.CR]

Complete list of metadatas

Cited literature [31 references] Display Hide Download

https://hal.inria.fr/hal-01112879
Contributor : Aurore Guillevic <>
Submitted on : Friday, June 3, 2016 - 2:27:01 AM
Last modification on : Wednesday, April 3, 2019 - 1:23:01 AM
Long-term archiving on : Sunday, September 4, 2016 - 10:10:21 AM

BGGM-Eurocrypt15.pdf

Publisher files allowed on an open archive

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

Files

Identifiers

Collections

Relations

Citation

Export

Metrics

851

691

Contact

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

Files

Identifiers

Collections

Relations

Citation

Export

Share

Metrics

851

691

Contact