Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!
Presented at the Annual IEEE Symposium on Foundations of Computer Science
We give a 2n+o(n)-time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic O (4n)-time and O(2n)-space algorithm of Micciancio and Voulgaris . We achieve our main result in three steps. First, we show how to modify the sampling algorithm from  to solve the problem of discrete Gaussian sampling over lattice shifts, L−t, with very low parameters. While the actual algorithm is a natural generalization of , the analysis uses substantial new ideas. This yields a 2n+o(n)-time algorithm for approximate CVP with the very good approximation factor γ = 1+2−o(n/ log n). Second, we show that the approximate closest vectors to a target vector t can be grouped into “lowerdimensional clusters,” and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that “behaves well with these clusters.” Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP. The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest.
|Logistics (theme 3)|
|Annual IEEE Symposium on Foundations of Computer Science|
|Organisation||Networks and Optimization|
Aggarwal, D, Dadush, D.N, & Stephens-Davidowitz, N. (2015). Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science 2015 (FOCS) (pp. 563–582). doi:10.1109/FOCS.2015.41