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

Taechan Kim; Razvan Barbulescu

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 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 , exTNFS allows to use this method when tackling whenever . This simple fact has consequences on the asymptotic complexity of NFS in the medium prime case, where the complexity is reduced from to , , respectively from to if multiple number fields are used. On the practical side, exTNFS can be used when and 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 Problem Number Field Sieve Finite Fields Cryptanalysis
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: 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},
      url = {https://eprint.iacr.org/2015/1027}
}