Abstract :
[en] 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 and remains as of today a
promising primitive for post-quantum cryptography. 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.
[fr] La cryptographie à base de réseaux euclidiens est aujourd'hui un domaine
scientifique en pleine expansion et connait une évolution rapide et accélérée
par l'attractivité du chiffrement complètement homomorphe ou des applications
multilinéaires cryptographiques. Ses propriétés sont très attractives : une
sécurité pouvant être réduite à la difficulté des pires cas de problèmes sur
les réseaux euclidiens, une efficacité asymptotique quasi-optimale et une
résistance présupposée aux ordinateurs quantiques. Cependant, on dénombre
encore peu de résultats de recherche sur les constructions à visée pratique
pour un niveau de sécurité fixé. Cette thèse s'inscrit dans cette direction et
travaille à réduire l’écart entre la théorie et la pratique de la
cryptographie à clé publique récente.
Dans cette thèse, nous concevons et implémentons une signature numérique basée
sur les réseaux euclidiens, deux schémas de chiffrement complètement
homomorphe et des applications multilinéaires cryptographiques.
Notre signature digitale ultra-performante, BLISS, ouvre la voie à la mise en
pratique de la cryptographie à base de réseaux sur petites architectures et
est un candidat sérieux à la cryptographie post-quantique. Nos schémas de
chiffrement complètement homomorphes permettent d'évaluer des circuits non
triviaux de manière compétitive. Finalement, nous proposons la première
implémentation d'applications multilinéaires et réalisons, pour la première
fois, un échange de clé non interactif entre plus de trois participants en
quelques secondes.
Institution :
Unilu - University of Luxembourg, Luxembourg
ENS Paris - École Normale Supérieure, Paris, France
