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.
Jury
Absract
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.
Homepage