Extended Tower Number Field Sieve: A New Complexity for the Medium Prime CaseReport as inadecuate




Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case - Download this document for free, or read online. Document in PDF available to download.

1 NTT Secure Platform Laboratories Tokyo 2 IMJ-PRG - Institut de Mathématiques de Jussieu - Paris Rive Gauche

Abstract : We introduce a new variant of the number field sieve algorithm for discrete logarithms in Fpn 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 polynomi-als to tackle discrete logs in Fpκ , exTNFS allows to use this method when tackling Fpηκ whenever gcdη, κ = 1. This simple fact has consequences on the asymptotic complexity of NFS in the medium prime case, where the complexity is reduced from LQ1-3, 3 96-9 to LQ1-3, 3 48-9, Q = p n , respectively from LQ1-3, 2.15 to LQ1-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 update the keysizes used for the associated pairings-based cryptosystems.

Keywords : Number Field Sieve Discrete Logarithm Problem Finite Fields Cryptanalysis





Author: Taechan Kim - Razvan Barbulescu -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents