CTL
31 mars 2009 - 15h30
Problèmes d'énumération dans les réseaux.
par Guillaume Hanrot de LORIA Equipe CACAO
Résumé : Un reseau euclidien est un sous-groupe discret de R^n, ou encore un quadrillage regulier dans R^n. En cryptographie mais aussi dans d'autres contextes (eg. codes correcteurs), etant donne un reseau, on est souvent amene a resoudre ou approcher les problemes suivants :
Trouver un vecteur non nul le plus court du reseau ;
Etant donne x in R^n, trouver un vecteur non nul du reseau le plus proche de x.
Ces deux problemes sont calculatoirement difficiles. La meilleure methode connue pour les resoudre est probabiliste, et exponentielle en temps et en espace. La meilleure methode deterministe, due a Kannan, est fondee sur une strategie d'enumeration, qui suit un long precalcul destine a calculer une base tres reduite du reseau. Nous presenterons une analyse detaillee de la strategie d'enumeration, montrant en particulier que la complexite de la recherche du vecteur le plus court est exactement $d^{d/(2e)(1+o(1))} poly(n)$ (ou $d$ est le cardinal d'une base du reseau), et donnerons un encadrement de la complexite optimale pour le probleme du vecteur le plus proche.
