Improved analysis of Kannan's shortest lattice vector algorithm

Guillaume Hanrot, Damien Stehlé

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

74 Citations (Scopus)

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 over twenty years. Kannan’s algorithm for solving the shortest vector problem (SVP) is in particular crucial in Schnorr’s celebrated block reduction algorithm, on which rely the best known generic attacks against the lattice-based encryption schemes mentioned above. In this paper we improve the complexity upper-bounds of Kannan’s algorithms. The analysis provides new insight on the practical cost of solving SVP, and helps progressing towards providing meaningful key-sizes.
Original languageEnglish
Title of host publicationAdvances in cryptology - CRYPTO 2007
EditorsAlfred Menezes
Place of PublicationBerlin/Heidelberg, Germany
PublisherSpringer, Springer Nature
Pages170-186
Number of pages17
ISBN (Print)9783540741428
DOIs
Publication statusPublished - 2007
EventAnnual International Cryptology Conference (27th : 2007) - Santa Barbara, CA, USA
Duration: 19 Aug 200723 Aug 2007

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume4622

Conference

ConferenceAnnual International Cryptology Conference (27th : 2007)
CitySanta Barbara, CA, USA
Period19/08/0723/08/07

Fingerprint Dive into the research topics of 'Improved analysis of Kannan's shortest lattice vector algorithm'. Together they form a unique fingerprint.

  • Cite this

    Hanrot, G., & Stehlé, D. (2007). Improved analysis of Kannan's shortest lattice vector algorithm. In A. Menezes (Ed.), Advances in cryptology - CRYPTO 2007 (pp. 170-186). (Lecture notes in computer science; Vol. 4622). Berlin/Heidelberg, Germany: Springer, Springer Nature. https://doi.org/10.1007/978-3-540-74143-5_10