Section: Overall Objectives

Presentation

The focus of this project is cryptanalysis, which is traditionally defined as the art of code-breaking: cryptanalysis studies the best attacks on cryptographic schemes, from a theoretical point of view (algorithm design) but also from a practical of view (implementation weaknesses, side-channel attacks). Cryptanalysis has a significant impact in the real world, because cryptographic algorithms and protocols, as well as keysizes, are selected based on the state-of-the-art in cryptanalysis. While provable security has made great advances in the past thirty years, it is alone insufficient to select cryptographic parameters: in general, choosing parameters based purely on security proofs leads to rather inefficient schemes. Cryptanalysis is therefore complementary of provable security, and both are essential to our understanding of security.

We consider cryptanalysis in the two worlds of cryptography: public-key cryptography (also called asymmetric cryptography) and secret-key cryptography (also called symmetric cryptography). Secret-key cryptography is much more efficient (and therefore more widespread) than public-key cryptography, but also less powerful because it requires to share secret keys: it encompasses symmetric encryption (stream ciphers, block ciphers), message authentication codes, and hash functions. Public-key cryptography provides more functionalities such as digital signatures, identity-based encryption and more generally functional encryption. Current public-key cryptographic techniques are based on advanced mathematics such as number theory (e.g. elliptic curves and lattices).

Inside public-key cryptanalysis, we focus on lattice techniques in particular, because lattice-based cryptography has been attracting considerable interest in the past few years, due to unique features such as potential resistance to quantum computers and new functionalities such as fully-homomorphic encryption  [33] (which allows to compute on encrypted data without requiring secret keys), noisy multi-linear maps  [31] and even (indistinguishability) obfuscation  [32] . These new functionalities have dramatically increased the popularity of lattice-based cryptography.

Inside secret-key cryptanalysis, we are especially interested in standard hash functions and the five SHA-3 finalists, due to the importance of the SHA-3 competition for a new hash function standard. We are also interested in the security of widespread symmetric ciphers, such as the AES block cipher standard (implemented in Intel processors) and the RC4 stream cipher (widely deployed in wireless protocols).

This project deals with both public-key cryptanalysis and secret-key cryptanalysis. Most of the researchers working in cryptanalysis only study one of the two, but there seems to be more and more interaction between the two fields, despite their apparent independence:

• For instance, coding theory techniques are now used in both secret-key cryptanalysis and public-key cryptanalysis: as an example, several standard hash functions implicitly use a linear code, and the properties of this code are related to the security of the hash function; and public-key cryptosystems based on coding theory problems have been studied for more than thirty years.

• Similarly, Groëbner bases and related techniques are now used in both secret-key cryptanalysis and public-key cryptanalysis: algebraic attacks on stream ciphers and block ciphers are now well-established, and there are still a few multivariate public-key cryptosystems, more than twenty years after the Matsumoto-Imai cryptosystem. Recently, techniques to solve systems of polynomial equations have been used in breakthrough results for solving the discrete logarithm problem over special finite fields and elliptic curves.

• As another example, time/memory tradeoffs are routinely used in both secret-key cryptanalysis and public-key cryptanalysis.

As a side objective, this project also aims at developing European-Chinese collaboration in cryptologic research.