Problème du vecteur le plus court dans un réseau : analyse de l'algorithme

Le problème (SVP) de trouver un vecteur non nul le plus court d'un réseau de $\R^n$ de dimension $d$ est un problème très classique ; au cours des dix dernières années, de nombreux travaux ont montré des bornes inférieures sur la complexité de ce problème. Ces résultats sont à la base des arguments de sécurité d'un certain nombre de cryptosystèmes (Ajtai-Dwork, NTRU). Le meilleur algorithme pratique pour ce problème, dû à Kannan, consiste à énumérer des points dans un ellipsoïde. Son analyse consiste classiquement à borner le nombre de points par le volume, qui est à son tour estimé par le volume du pavé circonscrit, donnant une complexité de $\tilde{O}(d^{d/2(1+o(1))})$. Nous montrons qu'une analyse plus fine conduit \`a une complexit\'e de $\tilde{O}(d^{d/(2e)(1+o(1))})$; ce résultat permet également d'améliorer la complexité des algorithmes de recherche du vecteur le plus proche (CVP), ou de calcul de bases "blocs-réduites" à la Schnorr.