Improved Analysis of Kannan's Shortest Lattice Vector Algorithm

Guillaume Hanrot 1 Damien Stehlé 2
1 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since more than twenty years. Kannan's algorithm for solving the shortest vector problem is in particular crucial in Schnorr's celebrated block reduction algorithm, on which are based the best known attacks against the lattice-based encryption schemes mentioned above. Understanding precisely Kannan's algorithm is of prime importance for providing meaningful key-sizes. In this paper we improve the complexity analyses of Kannan's algorithms and discuss the possibility of improving the underlying enumeration strategy.
Type de document :
Communication dans un congrès
Alfred Menezes. Advances in Cryptology - Crypto'07, Aug 2007, Santa Barbara, United States. Springer-Verlag, 4622, pp.170-186, 2007, LNCS. 〈10.1007/978-3-540-74143-5_10〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00145049
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 9 mai 2007 - 17:32:32
Dernière modification le : samedi 21 avril 2018 - 01:27:15
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:40:35

Fichiers

RR-6186.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Guillaume Hanrot, Damien Stehlé. Improved Analysis of Kannan's Shortest Lattice Vector Algorithm. Alfred Menezes. Advances in Cryptology - Crypto'07, Aug 2007, Santa Barbara, United States. Springer-Verlag, 4622, pp.170-186, 2007, LNCS. 〈10.1007/978-3-540-74143-5_10〉. 〈inria-00145049v2〉

Partager

Métriques

Consultations de la notice

342

Téléchargements de fichiers

170