Trap Me If You Can (Million Dollar Curve)

Joint work with Matthieu Finiasz, Cécile Delerablée, Louis Goubin, Tancrède Lepoint, and Matthieu Rivain

A longstanding problem in cryptography is the generation of publicly verifiable randomness. In particular, public verifiability allows to generate parameters for a cryptosystem in a way people can legitimately trust. There are many examples of standards using arbitrary constants which are now challenged and criticized for this reason, some of which even being suspected of containing a trap. Several sources of public entropy have already been proposed such as lotteries, stock market prices, the bitcoin blockchain, board games, or even Twitter and live webcams.

In this article, we propose a way of combining lotteries from several different countries that requires an adversary to manipulate several independent draws in order to introduce a trap in the generated cryptosystem. Each and every time a new source of public entropy is suggested, it receives its share of criticism for being “easy to manipulate”. We do not expect our solution to be an exception on this aspect, and will gladly receive any suggestion allowing to increase the confidence in the cryptosystem parameters we generate.

Our method allows to build what we call a Publicly verifiable RNG, from which we extract a seed that is used to instantiate and initialize a Blum-Blum-Shub random generator. We then use the binary stream produced by this generator as an input to a filtering function which deterministically outputs secure and uniformly distributed parameters from uniform bitstreams.

We apply our methodology to the ECDH cryptosystem, and propose the Million Dollar Curve as an alternative to curves P-256 and Curve25519.

Have a look at the Million Dollar Curve website for details!


Distinguishing Distributions Using Chernoff Information

Joint work with Pouyan Sepehrdad and Serge Vaudenay
Published in the Proceedings of ProvSec 2010

In this paper, we study the soundness amplification by repetition of cryptographic protocols. As a tool, we use the Chernoff Information. We specify the number of attempts or samples required to distinguish two distributions efficiently in various protocols. This includes weakly verifiable puzzles such as CAPTCHA-like challenge-response protocols, interactive arguments in sequential composition scenario and cryptanalysis of block ciphers. As our main contribution, we revisit computational soundness amplification by sequential repetition in the threshold case, i.e when completeness is not perfect. Moreover, we outline applications to the Leftover Hash Lemma and iterative attacks on block ciphers. I am part of the program committee of the 2011 edition of the ECRYPT Workshop on Lightweight Cryptography.


The Complexity of Distinguishing Distributions

Joint work with Serge Vaudenay
Published in the Proceedings of ICITS 2008

Cryptography often meets the problem of distinguishing distributions. In this paper we review techniques from hypothesis testing to express the advantage of the best distinguisher limited to a given number of samples. We link it with the Chernoff information and provide a useful approximation based on the squared Euclidean distance. We use it to extend linear cryptanalysis to groups with order larger than 2.


Linear Cryptanalysis of Non Binary Ciphers (with an Application to SAFER)

Joint work with Jacques Stern and Serge Vaudenay
Published in the Proceedings of SAC 2007

In this paper we re-visit distinguishing attacks. We show how to generalize the notion of linear distinguisher to arbitrary sets. Our thesis is that our generalization is the most natural one. We compare it with the one by Granboulan et al. from FSE’06 by showing that we can get sharp estimates of the data complexity and cumulate characteristics in linear hulls. As a proof of concept, we propose a better attack on their toy cipher TOY100 than the one that was originally suggested and we propose the best known plaintext attack on SAFER K/SK so far. This provides new directions to block cipher cryptanalysis even in the binary case. On the constructive side, we introduce DEAN18, a toy cipher which encrypts blocks of 18 decimal digits and we study its security.

PDF PS Slides

KFC - The Krazy Feistel Cipher

Joint work with Matthieu Finiasz
Published in the Proceedings of ASIACRYPT 2006

We introduce KFC, a block cipher based on a three round Feistel scheme. Each of the three round functions has an SPN-like structure for which we can either compute or bound the advantage of the best -limited adaptive distinguisher, for any value of . Using results from the decorrelation theory, we extend these results to the whole KFC construction. To the best of our knowledge, KFC is the first practical (in the sense that it can be implemented) block cipher to propose tight security proofs of resistance against large classes of attacks, including most classical cryptanalysis (such as linear and differential cryptanalysis, taking hull effect in consideration in both cases, higher order differential cryptanalysis, the boomerang attack, differential-linear cryptanalysis, and others).

PDF PS Slides BibTeX

Dial C for Cipher

Joint work with Matthieu Finiasz
Published in the Proceedings of SAC 2006

We introduce C, a practical provably secure block cipher with a slow key schedule. C is based on the same structure as AES but uses independent random substitution boxes instead of a fixed one. Its key schedule is based on the Blum-Blum-Shub pseudo-random generator, which allows us to prove that all obtained security results are still valid when taking into account the dependencies between the round keys. C is provably secure against several general classes of attacks. Strong evidence is given that it resists an even wider variety of attacks. We also propose a variant of C with simpler substitution boxes which is suitable for most applications, and for which security proofs still hold.

PDF PS Slides

Proving the Security of the AES Substitution-Permutation Network

Joint work with Serge Vaudenay
Published in the Proceedings of SAC 2005

In this paper we study the substitution-permutation network (SPN) on which AES is based. We introduce AES*, a SPN identical to AES except that fixed S-boxes are replaced by random and independent permutations. We prove that this construction resists linear and differential cryptanalysis with 4 inner rounds only, despite the huge cumulative effect of multipath characteristics that is induced by the symmetries of AES. We show that the DP and LP terms both tend towards very fast when the number of round increases. This proves a conjecture by Keliher, Meijer, and Tavares. We further show that AES* is immune to any iterated attack of order 1 after 10 rounds only, which substantially improves a previous result by Moriai and Vaudenay.

PDF PS Slides BibTeX

How Far Can we Go Beyond Linear Cryptanalysis?

Joint work with Pascal Junod and Serge Vaudenay
Published in the Proceedings of ASIACRYPT 2004

Several generalizations of linear cryptanalysis have been proposed in the past, as well as very similar attacks in a statistical point of view. In this paper, we define a rigorous general statistical framework which allows to interpret most of these attacks in a simple and unified way. Then, we explicitely construct optimal distinguishers, we evaluate their performance, and we prove that a block cipher immune to classical linear cryptanalysis possesses some resistance to a wide class of generalized versions, but not all. Finally, we derive tools which are necessary to set up more elaborate extensions of linear cryptanalysis, and to generalize the notions of bias, characteristic, and piling-up lemma.

PDF PS Slides BibTeX


Quantitative security of block ciphers : designs and cryptanalysis tools

(Very Short) Abstract: Block ciphers probably figure in the list of the most important cryptographic primitives. Although they are used for many different purposes, their essential goal is to ensure confidentiality. This thesis is concerned by their quantitative security, that is, by measurable attributes that reflect their ability to guarantee this confidentiality.

Full Text Table of Contents and Abstract Slides (private defense) Slides (public defense)

The importance of rigidity in cryptographic standards

These are the slides of a presentation I made on the 8th of May 2016 at the AWACS workshop, just before Eurocrypt 2016. This talk discusses the concept of rigidity: what it is, and why it is an important factor to consider in cryptographic standards. We provide several illustrations, based on real examples of existing or future standards, and discuss the strengths and weaknesses of each approach to rigidity.

Slides Slides (zipped Keynote file)

Talk on the Quantitative Security of Block Ciphers at the "Université Catholique de Louvain"

These are the slides of a presentation I made on the 5th of February 2009 at the Université Catholique de Louvain, where I was invited by Prof. Gildas Avoine from the Information Security Group.

Slides Slides (zipped Keynote file)

Invited Talk on Practical Decorrelation @ ESC'08

These are the slides of a presentation I made at ESC’08 in January. The talks is basically a survey on Serge Vaudenay’s decorrelation theory and on how we (with Matthieu Finiasz) used it to prove the security of two block ciphers constructions, namely C and KFC.


Tutorial on Provable Security in Cryptography

This tutorial is a compilation of some of my readings while I was preparing two lectures given at EPFL on provable security in cryptography. The topics covered include the basic security definitions for public-key & signature schemes, an introduction to game playing techniques, and several practical examples of proofs using games: ElGamal encryption, RF/RP Lemma, the Luby-Rackoff construction, the Full Domain Hash (FDH), and OAEP+.


Tutorial on Cryptosystems and LLL

Report realized during Prof. Amin Shokrollahi’s lectures on Algorithmic Number Theory. It provides a survey on lattices, LLL, and on two attacks proposed by Phong Nguyen on the GGH cryptosystem and on the implementation of El Gamal signatures in GPG 1.2.3.

PDF Slides

Report on Quantum Cryptography: On the Security of the BB84 Key-Exchange Protocol

Report realized during Prof. Arikan’s lectures on Quantum Computation and Quantum Information.

PDF Slides

Master Thesis: A Generalization of Linear Cryptanalysis

Master Thesis realized at the Cryptography & Security Laboratory (LASEC), EPFL, under the supervision of Prof. Vaudenay.

PDF Slides

Rapport sur la Factorisation de Grands Nombres à l'Aide de Courbes Elliptiques (in French)

Undergraduate semester project on the ECM method. This project was realized under the supervision of Jean Monnerat in March 2003.

PDF Slides

Rapport sur l'Attaque à Texte Chiffré Choisi contre PKCS#1 (in French)

Undergraduate semester project on Daniel Bleichenbacher’s attack against the RSA encryption standard. This project was realized under the supervision of Pascal Junod in 2002.

PDF Slides