Welcome to the resource topic for 2016/485
Title:
A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm
Authors: Palash Sarkar, 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.
ePrint: https://eprint.iacr.org/2016/485
Talk: https://www.youtube.com/watch?v=q_EsW8LLZDo
Slides: https://iacr.org/cryptodb/archive/2016/ASIACRYPT/presentation/27910.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .