The closest vector problem for some root lattices and orthogonal sieve algorithm

Abstract

La Cryptographie basée sur les réseaux euclidiens est née dans les années 1990 avec Miklos Ajtai où il démontre que les réseaux euclidiens peuvent servir de base solide à la cryptographie. La sécurité des cryptosystèmes basés sur les réseaux est basée sur la difficulté des problèmes du réseau tels que, les problèmes du vecteur le plus proche, et du vecteur le plus court. La cryptographie basé sur les réseaux connait aujourd’hui un essor rapide: son apparente résistance aux attaques quantiques, et surtout ses preuves de sécurité sous des hypothèses très précises de difficultés algorithmique de problèmes assez bien compris. Bien que les problèmes du vecteur le plus court et du vecteur le plus proche cités plus haut soient difficiles pour les réseaux, il existe certaines familles de réseaux pour lesquelles ces problèmes sont solubles en utilisant un algorithme polynomial. Nous avons par exemple les réseaux entiers Zn, les réseaux de racine An (n 1), Dn (n 2), E6, E7, E8, leurs duaux, et An Am, (n,m 1). Dans cette thèse nous proposons un algorithme polynomial de résolution du problème du vecteur le plus proche dans le réseaux Dn Dm (n,m 2). Nous considérons également le réseau An1 .. Ank (n1, ..., nk 1) pour lequel nous proposons un algorithme polynomial de résolution du problème du vecteur le plus proche. Cela a été fait en utilisant l’associativité des réseaux et la non commutativité du produit tensoriel. De plus, les algorithmes de crible ont été très efficaces pour résoudre certaines instances étendues du Problème du Vecteur le plus Court. Dans cette thèse, nous utilisons le fameux algorithme de réduction LLL et le symétrie des réseaux pour proposer un nouvel algorithme de crible pour les réseaux entier orthogonaux Zn. La cryptographie basée sur les réseaux Euclidiens progresse rapidement aujourd’hui grâce à son efficacité. Tout au long de ce travail, nous avons réussi à implémenter tous les algorithmes avec le logiciel informatique Maple 18.0