Cryptology ePrint Archive: Report 2016/684

Faster individual discrete logarithms with the QPA and NFS variants

Aurore Guillevic

Abstract: Computing discrete logarithms in finite fields is a main concern in cryptography. The best algorithms known are the Number Field Sieve and its variants (special, high-degree, tower) in large and medium characteristic fields (e.g. $\mathrm{GF}(p^2)$, $\mathrm{GF}(p^{12})$); the Function Field Sieve and the Quasi Polynomial-time Algorithm in small characteristic finite fields (e.g. $\mathrm{GF}(3^{6 \cdot 509})$). The last step of this family of algorithms is the individual logarithm computation. It computes a smooth decomposition of a given target in two phases: an initial splitting, then a descent tree. While new improvements have been made to reduce the complexity of the dominating relation collection and linear algebra steps, resulting in a smaller factor basis (database of known logarithms of small elements), the last step remains of same difficulty. Indeed, we have to find a smooth decomposition of a typically large element in the finite field. This work improves the initial splitting phase and applies to any non-prime finite field. It is very efficient when the extension degree is composite. It exploits the proper subfields, resulting in a much more smooth decomposition of the target. This leads to a new trade-off between the initial splitting step and the descent step with QPA. Moreover it reduces the width and the height of the subsequent descent tree.

Category / Keywords: public-key cryptography / Finite field, discrete logarithm, number field sieve, function field sieve, QPA

Date: received 7 Jul 2016, last revised 6 Aug 2017

Contact author: aurore guillevic at inria fr

Available format(s): PDF | BibTeX Citation

Version: 20170806:184336 (All versions of this report)

Short URL: ia.cr/2016/684

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]