Section: Overall Objectives

Highlights of the Year

• A spectacular new result has been obtained in the context of the cryptanalysis of the discrete logarithm problem in certain types of fields [22] . The complexity for solving this hard problem has been reduced from « sub-exponential » complexity, roughly $exp\left(O\left(n^{1/3}\right)\right)$ for an input size $n$, to the much lower « quasi-polynomial » complexity written as $exp\left(O\left({(logn)}^2\right)\right)$. As a result, a whole range of cryptographic proposals have lost momentum, notably proposals related to pairing-based cryptography over small characteristic fields.

• Still in the realm of the computation of discrete logarithm, a new record computation has been completed by the team for binary fields of prime extension degree [15] , using the Function Field Sieve algorithm. This establishes a useful comparison point between the Function Field Sieve and the newly proposed algorithm discussed above.

• The 2.0 release of the Cado-nfs software package, developed by the team, was made available in november. This releases incorporates an important number of improvements over the previous release which was 2 years earlier. Cado-nfs is available from the project page http://cado-nfs.gforge.inria.fr/ .