Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree
verfasst von : Taechan Kim, Jinhyuck Jeong
Erschienen in: Public-Key Cryptography – PKC 2017
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 compute a discrete logarithm in medium case in the running time of \(L_{p^n}(1/3, \root 3 \of {48/9})\) (resp. \(L_{p^n}(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_{p^n}(1/3, \root 3 \of {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, \root 3 \of {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.