Euclidean lattices: algorithms and cryptography

Réseaux Euclidiens : Algorithmes et Cryptographie

Damien Stehlé (1)

1 ARENAIRE - Computer arithmetic

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.

Les réseaux Euclidiens sont un riche objet algébrique qui apparaît dans des contextes variés en mathématiques et en informatique. Cette thèse considère plusieurs aspects algorithmiques des réseaux. Le concept de réduction d'une base d'un réseau est étudié minutieusement : nous couvrons en particulier le spectre complet des compromis qualité-temps des algorithmes de réduction. D'une part, nous présentons et analysons des algorithmes rapides pour trouver une base assez courte (base LLL-réduite) d'un réseau donné arbitraire. D'autre part, nous proposons de nouvelles analyses pour des algorithmes (plus lents) permettant de calculer des bases très courtes (bases HKZ et BKZ-réduites). Cette étude des algorithmes de résolution efficace de problèmes portant sur les réseaux est complétée par une application constructive exploitant leur difficulté apparente. Nous proposons et analysons des schémas cryptographiques, dont la fonction de chiffrement NTRU, et les prouvons au moins aussi difficiles à casser que de résoudre des problèmes pires-cas bien spécifiés portant sur les réseaux.

Mots clés: Euclidean lattices; LLL/HKZ/BKZ reductions; lattice-based cryptography; computer algebra; hybrid symbolic-numeric algorithms; analysis of algorithms.

Mots clés: Réseaux Euclidiens; réductions LLL/HKZ/BKZ; cryptographie reposant sur les réseaux Euclidiens; algorithmes hybrides numériques-algébriques; analyse d'algorithmes.

Domaines: Cryptographie et sécurité [cs.CR]; Algorithme et structure de données [cs.DS]

Damien Stehlé. Euclidean lattices: algorithms and cryptography. Cryptography and Security [cs.CR]. Ecole normale supérieure de lyon - ENS LYON, 2011. ⟨tel-00645387⟩