CVP / Exact · general ℓp norms

Solving the Closest Vector Problem with respect to ℓp Norms

Johannes Blömer · Stefanie Naewe

arXiv 1104.3720

PreprintSource checked

Time bound: poly(p, log r) · n^{(2 + o(1))n} arithmetic operations
Space bound: Polynomial in the encoded input size

Source / version date: 12 Jul 2011
Comparison variant: Exact · general ℓp norms
Cost scale: n^{c n + o(n)} arithmetic operations
Norm: Every fixed ℓp, 1 < p < ∞
target: Target in span(L); restrict to full-rank L ⊂ R^n
Preprocessing: Included
model: Deterministic arithmetic count with polynomial intermediate bit size
Success guarantee: Exact output
input: r bounds encoded basis/target coefficients; polynomial p-dependence suppressed

Assumptions and source notes

Version 3 improves the ℓp-family leading coefficient from 5/2 to 2 and explicitly bounds the working space and intermediate number sizes polynomially. The arXiv landing-page abstract remains stale; the original versioned PDF contains this stronger statement.

Source location

Abstract; Theorems 3.2 and 3.3; Corollary 6.5
Version: arXiv:1104.3720v3, 12 July 2011

Selected earlier references

Selected sources cited by this paper.

Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices
Johannes Blömer · 2000
States the earlier exact Euclidean n! algorithm and its polynomial-space bound. §1, algorithms for CVP, reference [Blö00]
Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
Guillaume Hanrot · Damien Stehlé · 2007
Compares its general-norm algorithm with Euclidean polynomial-space enumeration. §1, algorithms for CVP, reference [HS07]
A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
Daniele Micciancio · Panagiotis Voulgaris · 2013
Distinguishes its polynomial-space general-norm algorithm from Euclidean Voronoi computation. §1, algorithms for CVP, reference [MV10]

Primary source ↗

BibTeXDownload .bib

@misc{blomer-naewe-2011,
  author = {Johannes Blömer and Stefanie Naewe},
  title = {{Solving the Closest Vector Problem with respect to ℓp Norms}},
  year = {2011},
  url = {https://arxiv.org/abs/1104.3720},
  keywords = {CVP, lattice algorithms},
  cr_date = {2011-04-19},
  cr_status = {preprint},
  cr_venue = {arXiv:1104.3720},
  cr_author_ids = {johannes-blomer; stefanie-naewe},
  howpublished = {arXiv:1104.3720}
}