Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree

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 F-pn 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 compute a discrete logarithm in medium case in the running time of L-pn(1/3, (3)root 48/9) (resp. L-pn(1/3, 1.71) if multiple number fields are used), where n is an arbitrary composite. This should be compared with a recent variant by Sarkar and Singh (Asiacrypt 2016) that has the fastest running time of L-pn(1/3, (3)root 64/9) (resp. L-pn(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-pn(1/3, (3)root 32/9). On the practical side, we emphasize that the key-size of pairing-based cryptosystems should be updated following to our algorithm if the embedding degree n remains composite.