Discrete logarithms: Recent progress (and open problems)

Antoine Joux (CryptoExperts and University of Versailles Saint-Quentin-en-Yvelines)

Thursday, 07 November 2013, 13:00, B-IT Lecture Hall

In this talk, we present several recent improvements on the computation of discrete logarithms in finite fields. The first part presents a quasi-polynomial algorithm for computing discrete logarithms in fields of small characteristic. The main ingredient is a new method for generating multiplicative relations with a "systematic side" by composing the polynomial X^q-X with homographies.

The second part of the talk shows that the SNFS (special number field sieve) is not only an option for prime fields but can be generalized to extension fields, when the characteristic has a "sparse" expression. As a result, we obtain a variant of NFS with reduced complexity. In particular, this can be applied to some pairing-based constructions.