CVP / Exact · polyhedral norms

Solving the Closest Vector Problem with respect to ℓp Norms

Johannes Blömer · Stefanie Naewe

arXiv 1104.3720

PreprintSource checked

Time bound: (s log r)^O(1) · n^{(2 + o(1))n} arithmetic operations
Space bound: Polynomial space explicitly established in the 12 July v3 refinement

Source / version date: 16 May 2011
Comparison variant: Exact · polyhedral norms
Cost scale: n^{c n + o(n)} arithmetic operations
Norm: Rational polyhedral norm; centrally symmetric full-dimensional ball
target: Target in span(L); restrict to full-rank L ⊂ R^n
Preprocessing: Included
model: Deterministic arithmetic operation count
Success guarantee: Exact output
input: s inequalities; coefficient-size bound r

Assumptions and source notes

The 2 leading coefficient for rational polyhedral norms is already explicit in version 2. Its input-size factor depends polynomially on the number s of inequalities. Version 3 supplies a polynomial-space refinement without changing this coefficient.

Source location

Abstract; Theorems 3.2 and 3.3; compare v3 Theorem 3.2 for space
Version: arXiv:1104.3720v2, 16 May 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}
}