**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.

**Category / Keywords: **Discrete Logarithm Problem; Number Field Sieve; Finite Fields; Cryptanalysis

**Original Publication**** (with minor differences): **IACR-CRYPTO-2016

**Date: **received 23 Oct 2015, last revised 2 Jun 2016

**Contact author: **yoshiki1 at snu ac kr

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20160603:043536 (All versions of this report)

**Short URL: **ia.cr/2015/1027

[ Cryptology ePrint archive ]