Welcome to the resource topic for 2015/1027
Title:
Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case
Authors: Taechan Kim, 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.
ePrint: https://eprint.iacr.org/2015/1027
Talk: https://www.youtube.com/watch?v=a3VEG6nsOSk
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 .