Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
Crypto 2007
PublishedSource checked
- Time bound
- nn/(2e) + o(n)
- Space bound
- poly(n)
- Source / version date
- 7 May 2007
- Comparison variant
- Enumeration · superexponential scale
- Cost scale
- nc n + o(n)
- model
- Classical deterministic; polynomial space
Assumptions and source notes
Polynomial-space worst-case bound including the recursive basis preprocessing.
Source location
Introduction, main complexity bound
Version: 2007-05-07
Selected earlier references
Selected sources cited by this paper.
- Improved algorithms for integer programming and related lattice problems
Ravi Kannan · 1983
attributes the n^{n+o(n)} enumeration bound Introduction, PDF p. 2; reference [16]
- Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
Bettina Helfrich · 1985
attributes the n^{n/2+o(n)} refinement Introduction, PDF p. 2; §3.3; reference [13]
- Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
Improves the analysis of Kannan’s enumeration method for CVP. Introduction and CVP analysis
BibTeXDownload .bib
@inproceedings{hanrot-stehle-2007,
author = {Guillaume Hanrot and Damien Stehlé},
title = {{Improved Analysis of Kannan's Shortest Lattice Vector Algorithm}},
booktitle = {CRYPTO 2007},
year = {2007},
url = {https://arxiv.org/abs/0705.0965},
keywords = {SVP, enumeration, polynomial space},
cr_date = {2007-05-07},
cr_status = {published},
cr_venue = {CRYPTO 2007},
cr_author_ids = {guillaume-hanrot; damien-stehle}
}