Welcome to the resource topic for 2016/526
Title:
Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree
Authors: Taechan Kim, 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.
ePrint: https://eprint.iacr.org/2016/526
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 .