Date(s) : 12/03/2015 iCal
11 h 00 min - 12 h 00 min
This talk is about the asymptotic and practical hardness of discrete logarithms (DL) in non-prime finite fields of medium to large characteristic. This is needed to evaluate the security of e.g. pairing-based cryptosystems. The Number Field Sieve (NFS) algorithm is known to be the most efficient to compute discrete logarithms in prime finite fields and large characteristic finite fields. We are interested in adapting NFS for DL in GF(p^k), starting with k=2. NFS algorithm requires two number fields that can be embedded into GF(p^k). We introduce two new methods for polynomial selection, i.e. the choice of the two polynomials defining the two number fields involved in NFS. We generalize the Joux-Lercier method, and propose the Conjugation method.
These methods provide an important practical speed-up for DL in GF(p^2) compared to DL in prime fields of the same size. We show that by a record of DL computation in a field GF(p^2) of 180 decimal digits (p is 90 digit long).
Our methods have an asymptotic complexity of L(1/3,(64/9)^(1/3)). Moreover they can be applied in medium-sized characteristic and have in this case a better asymptotic complexity of L(1/3, (96/9)^(1/3)) instead of L(1/3, (128/9)^(1/3)). Compared to the recent MNFS paper, our asymtotic complexity is slightly better (2.20 vs 2.24 for the second constant in the L(1/3) formula).
This is a joint work with Razvan Barbulescu, Pierrick Gaudry and François Morain from the CATREL project (http://catrel.loria.fr).
Aurore Guillevic, Inria Nancy Grand Est, Équipe CARAMBA
Catégories