On the Closest Vector Problem with a Distance Guarantee
CCC 2014
- Time bound
- O(nN(1+log n/log(1/epsilon))) arithmetic operations
- Space bound
- N=O(n log(1/epsilon)/sqrt(epsilon)) dual vectors
- Source / version date
- 29 Sept 2014
- Comparison variant
- Classical · polynomial query and advice
- Cost scale
- Polynomial online time; radius in entry
- Decoding radius
- (1/2-2/(pi s_epsilon^2)) s_epsilon / eta_epsilon(L*), s_epsilon=sqrt(log(2(1+epsilon)/epsilon)/pi)
- Advice size
- N=O(n log(1/epsilon)/sqrt(epsilon)) samples from D_{L*,eta_epsilon(L*)}
- Preprocessing cost
- Unbounded; dual samples and matrix inverse prepared before the target
- Success guarantee
- There exists advice valid for all targets in the decoding ball
- Query model
- Arithmetic operations; epsilon inverse polynomial and 0 < epsilon < 1/200
Assumptions and source notes
Take epsilon inverse polynomial for polynomial advice and query cost. The matrix inverse can be stored during preprocessing. The radius depends on the lattice, rather than only lambda_1.
Source location
Theorem 3.1, printed pp. 13–14; §1.1
Version: 2014 author manuscript, corresponding to arXiv:1409.8063; first arXiv date shown, conference paper appeared earlier
Selected earlier references
Selected sources cited by this paper.
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
Jeffrey C. Lagarias · Hendrik W. Lenstra, Jr. · Claus-Peter Schnorr · 1990
Uses the O(n^{3/2}) search approximation as its historical benchmark. §1, previous best search-CVPP approximation [LLS90]
- Improved Inapproximability of Lattice and Coding Problems with Preprocessing
Oded Regev · 2004
Separates the earlier decision approximation from search CVPP. §1, decision-CVPP history [Reg04]
- Lattice Problems in NP ∩ coNP
Dorit Aharonov · Oded Regev · 2005
Uses the decision-estimator lineage for the gradient-based search algorithm. §1 and periodic Gaussian discussion [AR05]
- Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
Credits projection to a lattice with a close target as a reduction idea. Abstract; §1.1 and §5, reference [Kan87]
- On Bounded Distance Decoding for General Lattices
Yi-Kai Liu · Vadim Lyubashevsky · Daniele Micciancio · 2006
Improves the preprocessed hill-climbing decoder, its radius and the size of the dual-Gaussian advice. Abstract and §1.1; §3
- Lattice Problems in NP ∩ coNP
Dorit Aharonov · Oded Regev · 2005
Explains the predecessor periodic-Gaussian distance estimator and its dual-sampling representation. §1 introduction, Eq. (2)–(3)
@inproceedings{dadush-regev-stephens-davidowitz-2014,
author = {Daniel Dadush and Oded Regev and Noah Stephens-Davidowitz},
title = {{On the Closest Vector Problem with a Distance Guarantee}},
booktitle = {CCC 2014},
year = {2014},
url = {https://arxiv.org/abs/1409.8063},
keywords = {BDD, CVPP, preprocessing, distance guarantee},
cr_date = {2014-09-29},
cr_status = {published},
cr_venue = {CCC 2014},
cr_author_ids = {daniel-dadush; oded-regev; noah-stephens-davidowitz}
}