Paper 2015/1027

Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case

Taechan Kim and Razvan Barbulescu

Abstract

We introduce a new variant of the number field sieve algorithm for discrete logarithms in $\mathbb{F}_{p^n}$ called exTNFS. The most important modification is done in the polynomial selection step, which determines the cost of the whole algorithm: if one knows how to select good polynomials to tackle discrete logarithms in $\mathbb{F}_{p^\kappa}$, exTNFS allows to use this method when tackling $\mathbb{F}_{p^{\eta\kappa}}$ whenever $\gcd(\eta,\kappa)=1$. This simple fact has consequences on the asymptotic complexity of NFS in the medium prime case, where the complexity is reduced from $L_Q(1/3,\sqrt[3]{96/9})$ to $L_Q(1/3,\sqrt[3]{48/9})$, $Q=p^n$, respectively from $L_Q(1/3,2.15)$ to $L_Q(1/3,1.71)$ if multiple number fields are used. On the practical side, exTNFS can be used when $n=6$ and $n=12$ and this requires to updating the keysizes used for the associated pairing-based cryptosystems.

Note: This is a merged version of two consecutive papers, eprint 2015/1027 and eprint 2015/1076.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Keywords
Discrete Logarithm ProblemNumber Field SieveFinite FieldsCryptanalysis
Contact author(s)
yoshiki1 @ snu ac kr
History
2016-06-03: last of 2 revisions
2015-10-26: received
See all versions
Short URL
https://ia.cr/2015/1027
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1027,
      author = {Taechan Kim and Razvan Barbulescu},
      title = {Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1027},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1027}},
      url = {https://eprint.iacr.org/2015/1027}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.