• Aurore Guillevic, Equipe Grace, INRIA Saclay- Île de France et LIX – Polynomial selection for NFS-DL in non-prime finite fields

This talk is about the asymptotic and practical hardness of discrete logarithms in non-prime finite fields. 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. These methods provide an important practical speed-up for DL in GF(p^2) compared to DL in prime fields of the same size, as showed the recent record of DL computation in GF(p^2) (announcement at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1406&L=NMBRTHRY&F=&S=&P=5520). 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)).

This is a joint work with Razvan Barbulescu, Pierrick Gaudry and François Morain from the CATREL team.

  • Hoeteck Wee, LIENS, ENS, – Functional Encryption and its Impact on Cryptography

Functional encryption is a novel paradigm for public-key encryption that enables both fine-grained access control and selective computation on encrypted data, as is necessary to protect big, complex data in the cloud. In this talk, we provide a brief introduction to functional encryption, and an overview of its overarching impact on the field of cryptography.

  • Ayoub Otmani, LITIS, Université de Rouen – Key-Recovery Techniques in Code-Based Cryptography

An important step in the design of secure cryptographic primitives consists in identifying hard algorithmic problems. Despite the fact that several problems have been proposed as a foundation for public-key primitives, those effectively used are essentially classical problems coming from integer factorisation and discrete logarithm. On the other hand, coding theory appeared with the goal to solve the challenging problem of decoding a random linear code. It is widely admitted as a hard problem that has led McEliece in 1978 to propose the first code-based public-key encryption scheme. The key concept is to focus on codes that come up with an efficient decoding algorithm. McEliece recommended the use of binary Goppa codes which proved to be, up to now, a secure choice.

This talk will explore the important notion underlying code-based cryptography in order to understand its strengths and weaknesses. We then look at different extensions that lead to a wide range of variants of the McEliece scheme. This will give the opportunity to describe efficient and practical key-recovery cryptanalysis on these schemes, and to show the large diversity in the design of these attacks

  • 15h30 : Frédéric de Portzamparc, Gemalto – Polsys (Inria/UPMC/CNRS) – Algebraic Attack against Wild McEliece & Incognito

In this talk, we present a new algebraic attack against Wild McEliece & Wild McEliece Incognito, which are generalizations of the original McEliece cryptosystem introduced by Bernstein, Lange and Peters (BLP).

We prove that, thanks to the multiple factors in the Goppa polynomial, recovering the secret key for such schemes is equivalent to solving a system of polynomial equations whose solutions have the structure of a usual vector space. Consequently, to recover a basis of this vector space, we can greatly reduce the number of variables in the corresponding algebraic system. From these solutions, we can then deduce the basis of a GRS code. Finally, the last step of the cryptanalysis of those schemes corresponds to attacking a McEliece scheme instantiated with particular GRS codes (with a polynomial relation between the support and the multipliers) which can be done in polynomial-time thanks to a variant of the Sidelnikov-Shestakov attack. For Wild McEliece & Incognito, we also show that solving the corresponding algebraic system is notably easier in the case of a non-prime base field Fq.

To support our theoretical results, we have been able to practically break several parameters defined over a non-prime base field $q \in \{9,16,25,27, 32\}$, $t\leq 6$, extension degrees $m \in \{2,3\}$, and security level up to $2^{129}$ against information set decoding in few minutes or hours. Amongst others, we broke the hardest challenges proposed for q=27 by BLP (on the website http://pqcrypto.org/wild-challenges.html), which were out of the reach of the attack of Couvreur, Otmani and Tillich.

Joint work with Jean-Charles Faugère and Ludovic Perret.