The Tower Number Field Sieve

Razvan Barbulescu; Pierrick Gaudry; Thorsten Kleinjung

Paper 2015/505 Original: eprint.iacr.org/2015/505 ↗

The Tower Number Field Sieve

Razvan Barbulescu

Pierrick Gaudry

Thorsten Kleinjung

Abstract

The security of pairing-based crypto-systems relies on the difficulty to compute discrete logarithms in finite fields GF(p^n) where n is a small integer larger than 1. The state-of-art algorithm is the number field sieve (NFS) together with its many variants. When p has a special form (SNFS), as in many pairings constructions, NFS has a faster variant due to Joux and Pierrot. We present a new NFS variant for SNFS computations, which is better for some cryptographically relevant cases, according to a precise comparison of norm sizes. The new algorithm is an adaptation of Schirokauer's variant of NFS based on tower extensions, for which we give a middlebrow presentation.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2015-05-27: last updated; 2015-05-27: published
Short URL: https://ia.cr/2015/505
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2015/505,
      author = {Razvan Barbulescu and Pierrick Gaudry and Thorsten Kleinjung},
      title = {The Tower Number Field Sieve},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/505},
      year = {2015},
      url = {https://eprint.iacr.org/2015/505}
}