Design and Implementation
of Lattice-Based Cryptography
Bringing lattice-based cryptography from theoretical constructions to working implementations.
Three ways to make the theory work.
Smaller, practical signatures
BLISS uses lattice-based cryptography to sign messages. Bimodal Gaussian sampling helps make signatures compact and efficient.
Computing on encrypted data
Two fully homomorphic encryption schemes turn the promise of computing without decryption into implementations that evaluate nontrivial circuits.
Implementing multilinear maps
The thesis presents the first implementation of cryptographic multilinear maps, demonstrating a then-new route to multiparty non-interactive key exchange.
A coin flip that makes a difference.
A lattice signature must not reveal its secret key. Rejection sampling filters candidate signatures to remove the information that would give the secret away. BLISS draws candidates around either of two opposite shifts, chosen with a coin flip. This bimodal distribution makes rejection sampling more efficient.
BLISS and CRYSTALS-Dilithium belong to the broader family of lattice signatures using rejection sampling. Their sampling choices differ: BLISS uses bimodal Gaussians; Dilithium uses uniform sampling to simplify secure implementation. Read the Dilithium design background ↗
Original abstract · 2014
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.