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 $n$ is a power of prime 2. When $p$ is of special form, the complexity is further reduced to $L_{p^n}(1/3, \sqrt[3]{32/9})$. On the practical side, we emphasize that the keysize of pairing-based cryptosystems should be updated following to our algorithm if the embedding degree $n$ remains composite.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Discrete Logarithm ProblemNumber Field SieveFinite FieldsCryptanalysis
Contact author(s)
yoshiki1 @ snu ac kr
History
2016-10-06: revised
2016-05-29: received
See all versions
Short URL
https://ia.cr/2016/526
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/526,
      author = {Taechan Kim and Jinhyuck Jeong},
      title = {Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree},
      howpublished = {Cryptology ePrint Archive, Paper 2016/526},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/526}},
      url = {https://eprint.iacr.org/2016/526}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.