Paper 2016/526

Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree

Taechan Kim and Jinhyuck Jeong

Abstract

We propose a generalization of exTNFS algorithm recently introduced by Kim and Barbulescu (CRYPTO 2016). The algorithm, exTNFS, is a state-of-the-art algorithm for discrete logarithm in ${\mathbb{F}}_{p^n}$ in the medium prime case, but it only applies when $n=\eta \kappa$ is a composite with nontrivial factors $\eta$ and $\kappa$ such that $gcd(\eta ,\kappa )=1$. Our generalization, however, shows that exTNFS algorithm can be also adapted to the setting with an arbitrary composite $n$ maintaining its best asymptotic complexity. We show that one can solve discrete logarithm in medium case in the running time of $L_{p^n}(1/3,\sqrt[3]{48/9})$ (resp. $L_{p^n}(1/3,1.71)$ if multiple number fields are used), where $n$ is an \textit{arbitrary composite}. This should be compared with a recent variant by Sarkar and Singh (Asiacrypt 2016) that has the fastest running time of $L_{p^n}(1/3,\sqrt[3]{64/9})$ (resp. $L_{p^n}(1/3,1.88)$) when $$ is a power of prime 2. When $$ is of special form, the complexity is further reduced to $$. On the practical side, we emphasize that the keysize of pairing-based cryptosystems should be updated following to our algorithm if the embedding degree $$ remains composite.