Design and Implementation of Lattice-Based Cryptography, defended in June 2014 at École Normale Supérieure (advisor David Pointcheval) and University of Luxembourg (advisor Jean-Sébastien Coron). Awarded the 2014 Gilles Kahn Prize by the Informatics Society of France.
The thesis designs and implements a lattice-based signature scheme (BLISS), two fully homomorphic encryption schemes, and the first implementation of cryptographic multilinear maps. The idea I am fondest of is the one at the core of BLISS. A lattice signature must not leak the secret key, so candidate signatures are filtered by rejection sampling: keep a candidate with the right probability and the output distribution is independent of the secret. Earlier schemes sampled around one secret-dependent center and had to reject often to hide it. BLISS flips a coin and samples around ± the center: the two shifted Gaussians average into a distribution that is already almost centered, so far fewer candidates are thrown away and signatures shrink.
BLISS opened the way to implementing lattice-based signatures on constrained devices, and rejection sampling on bimodal Gaussians lives on in the design lineage that led to CRYSTALS-Dilithium and the ML-DSA standard.
Today, lattice-based cryptography is a thriving scientific field. Its swift expansion is due, among others, to the attractiveness of fully homomorphic encryption and cryptographic multilinear maps. Lattice-based cryptography has also been recognized for its thrilling properties: a security that can be reduced to worst-case instances of problems over lattices, a quasi-optimal asymptotic efficiency and an alleged resistance to quantum computers. However, its practical use in real-world products leaves a lot to be desired. This thesis accomplishes a step towards this goal by narrowing the gap between theoretical research and practical implementation of recent public key cryptosystems.
In this thesis, we design and implement a lattice-based digital signature, two fully homomorphic encryption schemes and cryptographic multilinear maps. Our highly efficient signature scheme, BLISS, opened the way to implementing lattice-based cryptography on constrained devices. Our fully homomorphic encryption schemes enjoy competitive homomorphic evaluations of nontrivial circuits. Finally, we describe the first implementation of cryptographic multilinear maps. Based on our implementation, a non-interactive key exchange between more than three parties has been realized for the first time, and amounts to a few seconds per party.