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 .