Gödel Prize Winner Antoine Joux speaks at B-IT
 | |
|
The 2013 Gödel Prize was awarded to Antoine Joux (shared with two others) for his "One RoundProtocol for Tripartite Diffie-Hellman." This work generalizes the two-party key agreement of Diffie and Hellman to a multi-party key exchange with a focus on the three-party case. The prize is one of the highest awards in theoretical computer science and bestowed by the ACM SIGACT and EATCS.
The two fundamental problems for public key cryptography are integer factorization and discrete logarithms. Historically, progress on both problems has gone hand in hand -- until recently Antoine Joux surprised the cryptographic community with an amazingly fast discrete logarithm computation in certain fields. No matching improvement for integer factorization is in sight.
On Thursday, 07 November 2013, 13:00 sharp, at B-IT's Lecture Hall
Antoine Joux (CryptoExperts and University of Versailles Saint-Quentin-en-Yvelines)
will speak on
Discrete logarithms: Recent progress (and open problems)
Abstract: 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.