TY - GEN
T1 - On the closest vector problem with a distance guarantee
AU - Dadush, Daniel
AU - Regev, Oded
AU - Stephens-Davidowitz, Noah
PY - 2014
Y1 - 2014
N2 - We present a new efficient algorithm for the search version of the approximate Closest Vector Problem with Preprocessing (CVPP). Our algorithm achieves an approximation factor of O(n√log n), improving on the previous best of O(n1.5) due to Lag arias, Lenstra, and Schnorr {hkzbabai}. We also show, somewhat surprisingly, that only O(n) vectors of preprocessing advice are sufficient to solve the problem (with the slightly worse approximation factor of O(n)). We remark that this still leaves a large gap with respect to the decisional version of CVPP, where the best known approximation factor is O(√n/log n) due to Aharonov and Regev [2]. To achieve these results, we show a reduction to the same problem restricted to target points that are close to the lattice and a more efficient reduction to a harder problem, Bounded Distance Decoding with preprocessing (BDDP). Combining either reduction with the previous best-known algorithm for BDDP by Liu, Lyubashevsky, and Micciancio [3] gives our main result. In the setting of CVP without preprocessing, we also give a reduction from (1+ε)γ approximate CVP to γ approximate CVP where the target is at distance at most 1+1/ε times the minimum distance (the length of the shortest non-zero vector) which relies on the lattice sparsification techniques of Dadush and Kun [4]. As our final and most technical contribution, we present a substantially more efficient variant of the LLM algorithm (both in terms of run-time and amount of preprocessing advice), and via an improved analysis, show that it can decode up to a distance proportional to the reciprocal of the smoothing parameter of the dual lattice [5]. We show that this is never smaller than the LLM decoding radius, and that it can be up to an wide tilde Ω(√n) factor larger.
AB - We present a new efficient algorithm for the search version of the approximate Closest Vector Problem with Preprocessing (CVPP). Our algorithm achieves an approximation factor of O(n√log n), improving on the previous best of O(n1.5) due to Lag arias, Lenstra, and Schnorr {hkzbabai}. We also show, somewhat surprisingly, that only O(n) vectors of preprocessing advice are sufficient to solve the problem (with the slightly worse approximation factor of O(n)). We remark that this still leaves a large gap with respect to the decisional version of CVPP, where the best known approximation factor is O(√n/log n) due to Aharonov and Regev [2]. To achieve these results, we show a reduction to the same problem restricted to target points that are close to the lattice and a more efficient reduction to a harder problem, Bounded Distance Decoding with preprocessing (BDDP). Combining either reduction with the previous best-known algorithm for BDDP by Liu, Lyubashevsky, and Micciancio [3] gives our main result. In the setting of CVP without preprocessing, we also give a reduction from (1+ε)γ approximate CVP to γ approximate CVP where the target is at distance at most 1+1/ε times the minimum distance (the length of the shortest non-zero vector) which relies on the lattice sparsification techniques of Dadush and Kun [4]. As our final and most technical contribution, we present a substantially more efficient variant of the LLM algorithm (both in terms of run-time and amount of preprocessing advice), and via an improved analysis, show that it can decode up to a distance proportional to the reciprocal of the smoothing parameter of the dual lattice [5]. We show that this is never smaller than the LLM decoding radius, and that it can be up to an wide tilde Ω(√n) factor larger.
KW - BDD
KW - BDDP
KW - CVP
KW - CVPP
UR - http://www.scopus.com/inward/record.url?scp=84906658974&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906658974&partnerID=8YFLogxK
U2 - 10.1109/CCC.2014.18
DO - 10.1109/CCC.2014.18
M3 - Conference contribution
AN - SCOPUS:84906658974
SN - 9781479936267
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 98
EP - 109
BT - Proceedings - IEEE 29th Conference on Computational Complexity, CCC 2014
PB - IEEE Computer Society
T2 - 29th Annual IEEE Conference on Computational Complexity, CCC 2014
Y2 - 11 June 2014 through 13 June 2014
ER -