Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields - Archive ouverte HAL Access content directly
Conference Papers Year : 2015

Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields

(1, 2, 3) , (3) , (1, 2) , (1, 2)
1
2
3

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 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^2)$ whose cardinality is 180 digits (595 bits) long.
Fichier principal
Vignette du fichier
BGGM-Eurocrypt15.pdf (477.27 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-01112879 , version 1 (03-02-2015)
hal-01112879 , version 2 (03-06-2016)

Identifiers

Cite

Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, François Morain. Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields. EUROCRYPT 2015, Proceedings, Part {I}, Apr 2015, Sofia, Bulgaria. pp.129-155, ⟨10.1007/978-3-662-46800-5_6⟩. ⟨hal-01112879v2⟩
976 View
1020 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More