Réseaux Euclidiens : Algorithmes et Cryptographie

Euclidean lattices: algorithms and cryptography

The manuscript (without appendices): pdf.
The full manuscript (with appendices): pdf.
The slides of the defense: pdf.


President: Karim BELABAS
Reviewers: Arjen LENSTRA
Examiners: Pascal KOIRAN
Brigitte VALLÉE
Chee K. YAP


Euclidean lattices are a rich algebraic object that occurs in a wide variety of contexts in mathematics and in computer science. The present thesis considers several algorithmic aspects of lattices. The concept of lattice basis reduction is thoroughly investigated: in particular, we cover the full range of time-quality trade-offs of reduction algorithms. On the first hand, we describe and analyse fast algorithms for finding a relatively short basis (LLL-reduced basis) of an arbitrary given lattice. On the second hand, we propose novel analyses for (slower) algorithms that compute very short bases (HKZ-reduced and BKZ-reduced bases). This study on how to efficiently solve algorithmic problems on lattices is completed by a constructive application exploiting their apparent hardness. We propose and analyze cryptographic schemes, including the NTRU encryption function, and prove them at least as secure as well-specified worst-case problems on lattices.