Research in Cryptography

Cryptographic algorithms play a crucial role in the information society. When we use bank card or credit card, call someone on a mobile phone, get access to health case services, or buy something on the web, cryptographic algorithms protect us. These algorithms ensure that our transactions and bank accounts are safe, that nobody can eavesdrop on our mobile, VoIP or instant messaging communications and that sensitive health data is protected from unauthorized access. Cryptographic protocols can also provide digital signatures, user and data authentication, and more advanced functionalities such as electronic money or electronic voting. Information technology is expanding further and in the short term we expect to see more of e-government, e-voting, e-commerce.

Cryptography has two complementary aspects: public-key cryptography, and private-key cryptography.

Public-key (or Asymmetric) Cryptography is a concept invented by Diffie and Hellman in 1976. It allows users to communicate securely without having prior access to a shared secret key, by using a pair of cryptographic keys, designated as public key and private key, which are related mathematically. Public-key cryptography is generally based on some number-theoretic primitive, such as exponentation modulo an integer of unknown factorization, or computation in the group of points of a well chosen elliptic curve.

The modern approach in public-key cryptography is the provable security approach. Proving the security of a cryptosystem consists in first formalizing the security notions that should be reached by the cryptosystem, which in turn can be established by means of a mathematical proof. Security proofs are most often relative: one shows that a certain security notion is reached, assuming the hardness of some well-defined computational problem. Provable security is mainstream in today's cryptography.

Cryptography is about making schemes that accomplish some goal despite the presence of an adversary. To formalize the security of a cryptosystem, one must therefore specify what the adversary is allowed to do, and when the attack is successful. A cryptosystem will be said "secure" if one can show that such attack is impossible (except maybe with negligible probability), under some complexity assumption (for example, factoring large integers is hard). For example, for a public-key encryption scheme, one might consider that the attacker's goal is to recover the private-key from the public-key. But this is actually a very ambitious goal (which corresponds to a total break of the scheme). In practice, the attacker could be pursuing a more modest goal, for example recovering the plaintext given the corresponding ciphertext, or even obtaining only one bit of information about the plaintext.

Correctly formalizing the security of a cryptographic functionality is not an easy task. For signature schemes, the first satisfying security notion was obtained only in 1988 (this is the existential unforgeability under a chosen message attack notion, defined by S. Goldwasser, S. Micali and R. Rivest in "A digital signature scheme secure against adaptive chosen-message attacks", SIAM J. of computing, 1988).

For public-key encryption schemes, the first satisfying notion was obtained only in 1991 (this is the semantic security under an adaptive chosen ciphertext attack, defined by Charles Rackoff and Daniel R. Simon in "Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack", CRYPTO '91: Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology). Correctly defining a security notion is however crucially important: one cannot hope to obtain a secure scheme if one doesn't know which properties a secure scheme is supposed to achieve!

Once the security notion has been correctly formalized, the second step consists in constructing a scheme that provably satisfies this definition. The security proof is most often a proof by reduction: one shows that if the security notion was not satisfied, that is, if there was an attacker able to break the scheme, then using this attacker one could efficiently solve a mathematical problem believed to be hard to solve (for example, factoring large integers). Therefore, the security of a cryptographic scheme is most often relative: security is based on a widely believe complexity assumption (for example, factoring large integers is hard). The field of provable security is the combination of those three steps: definition, scheme, and proof of security. This approach is now the mainstream in the cryptographic research community. Our goal in LACS is to advance the state of the art in the field of security for e-commerce, while following this approach which has proved crucial in building trustable cryptographic schemes.

Private-Key (or Symmetric) Cryptography is about constructing efficient and secure primitives in the shared secret-key setting. Block-ciphers, stream ciphers, cryptographic hash functions and message authentication codes are fundamental primitives with the help of which most today's security protocols are built due to the high speed and convenience of use they offer. During the last few years, we have seen an increasing number of papers which prove certain security properties of the new schemes. However, the scope of these proofs is still very limited (typically resistance is shown against a narrow class of attacks). In order to improve our understanding of the security and to increase our confidence in the current and future algorithms, there is still a need for developing new methods to assess their security and to develop new attacks and designs ideas.

In the context of this research unit, we plan to address the following topics: study of novel algebraic attacks on block ciphers and stream ciphers; continue some of our previous work on structural cryptanalysis of schemes; extensions of differential, linear, slide attacks. Development of new methods for the analysis of hash functions and message-authentication codes (MACs), as recent results show that this area has been significantly under-studied. In this context, we will continue to work extensively with industry and standardization bodies as partner in research and development projects, as we did in the past. For example, we worked on European pre-standardization project for encryption primitives (NESSIE) (the project has won a European commission excellence award), and in a road-map for cryptography projects STORK. We have also been actively involved and will continue to evaluate current and future industry standards for GSM, wireless and Internet communications.