Abstract - stehle (original) (raw)
S�minaire du 12 mars 07, Damien Stehl�, CNRS, LIP-ENS Lyon, Projet Arenaire
Am�lioration de l'analyse de l'algorithme de Kannan pour r�soudre SVP
Le probl�me du vecteur le plus court d'un r�seau euclidien est NP-difficile sous des r�ductions randomis�es. Plusieurs cryptosyst�mes reposent sur des variantes affaiblies de ce probl�me. Pour cette raison, il est important de conna�tre pr�cis�ment la complexit� des algorithmes qui le r�solvent. Le plus classique d'entre eux, et le seul � �tre pratique, est l'algorithme de Kannan. Nous am�liorons sa meilleure borne de complexit� connue et g�n�ralisons notre analyse � d'autres probl�mes difficiles sur les r�seaux euclidiens.
Travail en commun avec Guillaume Hanrot.
Last modified: Mon May 23 18:32:54 CEST 2005