Cryptology ePrint Archive: Report 2015/505

The Tower Number Field Sieve

Razvan Barbulescu and Pierrick Gaudry and 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.

Category / Keywords: public-key cryptography / discrete logarithm, number field sieve, pairings

Date: received 27 May 2015

Contact author: razvan barbaud at imj-prg fr

Available format(s): PDF | BibTeX Citation

Version: 20150527:192156 (All versions of this report)

Short URL: ia.cr/2015/505

Discussion forum: Show discussion | Start new discussion