Paper 2016/485

A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm

Palash Sarkar and Shashank Singh

Abstract

In a recent work, Kim and Barbulescu had extended the tower number field sieve algorithm to obtain improved asymptotic complexities in the medium prime case for the discrete logarithm problem on $\mathbb{F}_{p^n}$ where $n$ is not a prime power. Their method does not work when $n$ is a composite prime power. For this case, we obtain new asymptotic complexities, e.g., $L_{p^n}(1/3,(64/9)^{1/3})$ (resp. $L_{p^n}(1/3,1.88)$ for the multiple number field variation) when $n$ is composite and a power of 2; the previously best known complexity for this case is $L_{p^n}(1/3,(96/9)^{1/3})$ (resp. $L_{p^n}(1/3,2.12)$). These complexities may have consequences to the selection of key sizes for pairing based cryptography. The new complexities are achieved through a general polynomial selection method. This method, which we call Algorithm-$\mathcal{C}$, extends a previous polynomial selection method proposed at Eurocrypt 2016 to the tower number field case. As special cases, it is possible to obtain the generalised Joux-Lercier and the Conjugation method of polynomial selection proposed at Eurocrypt 2015 and the extension of these methods to the tower number field scenario by Kim and Barbulescu. A thorough analysis of the new algorithm is carried out in both concrete and asymptotic terms.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Discrete LogTower Number Field Sieve
Contact author(s)
sha2nk singh @ gmail com
History
2016-05-20: last of 2 revisions
2016-05-20: received
See all versions
Short URL
https://ia.cr/2016/485
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/485,
      author = {Palash Sarkar and Shashank Singh},
      title = {A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2016/485},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/485}},
      url = {https://eprint.iacr.org/2016/485}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.