CVP / CVP with preprocessing · query cost

A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations

Daniele Micciancio · Panagiotis Voulgaris

SIAM Journal on Computing 2013

PublishedSource checked

Time bound: Õ(2²ⁿ) query time
Space bound: Õ(2ⁿ) stored advice

Source / version date: 2011
Comparison variant: CVP with preprocessing · query cost
Cost scale: 2^{c n + o(n)}
norm: Euclidean ℓ₂
preprocessing: Õ(4^n) time; not included in query score
advice: At most 2(2^n−1) Voronoi-relevant vectors
target: Arbitrary target
success: Deterministic exact output

Assumptions and source notes

Exact online CVP given the list of Voronoi-relevant vectors. Theorem 4.2 costs Õ(2^n |VR|), and |VR| ≤ 2(2^n−1). The lattice-only Voronoi computation costs Õ(4^n) and is excluded from query time. The original 2011 chapter explicitly presents the 2^{2n} time / 2^n space Voronoi result. The separate 22-page author full version is dated 8 December 2010, but its first public date is unverified. A conservative public-by-2011 date is therefore supported without backdating the result to the original 2010 conference abstract.

Source location

Original 2011 chapter, introduction and Table 1, PDF p. 3; §3.1, PDF pp. 8–10; end of §3.2, PDF p. 13
Version: Original uncorrected IWCC 2011 author PDF

Selected earlier references

Selected sources cited by this paper.

Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
Uses enumeration as the earlier superexponential exact-CVP benchmark. Introduction; references [Kan87]
Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
Guillaume Hanrot · Damien Stehlé · 2007
Uses the rank-reduction lineage in the Voronoi algorithm. §4.2 rank reduction, references [HS07]

Primary source ↗

BibTeXDownload .bib

@misc{paper-a68a0bb5d70f,
  author = {Daniele Micciancio and Panagiotis Voulgaris},
  title = {{A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations}},
  journal = {SIAM Journal on Computing},
  year = {2013},
  doi = {10.1137/100811970},
  url = {https://eccc.weizmann.ac.il/report/2010/014/},
  cr_date = {2012-03-03},
  cr_status = {published},
  cr_venue = {SIAM Journal on Computing},
  cr_author_ids = {daniele-micciancio; panagiotis-voulgaris},
  howpublished = {SIAM Journal on Computing; ECCC TR10-014, revised 3 March 2012}
}