The discrete Gaussian @math is the distribution that assigns to each vector @math in a shifted lattice @math probability proportional to @math . It has long been an important tool in the study of lattices. More recently, algorithms for discrete Gaussian sampling (DGS) have found many applications in computer science. In particular, polynomial-time algorithms for DGS with very high parameters @math have found many uses in cryptography and in reductions between lattice problems. And, in the past year, Aggarwal, Dadush, Regev, and Stephens-Davidowitz showed @math -time algorithms for DGS with a much wider range of parameters and used them to obtain the current fastest known algorithms for the two most important lattice problems, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Motivated by its increasing importance, we investigate the complexity of DGS itself and its relationship to CVP and SVP. Our first result is a polynomial-time dimension-preserving reduction from DGS to CVP. There is a simple reduction from CVP to DGS, so this shows that DGS is equivalent to CVP. Our second result, which we find to be more surprising, is a polynomial-time dimension-preserving reduction from centered DGS (the important special case when @math ) to SVP. In the other direction, there is a simple reduction from @math -approximate SVP for any @math , and we present some (relatively weak) evidence to suggest that this might be the best achievable approximation factor. We also show that our CVP result extends to a much wider class of distributions and even to other norms.
However, all of the above-mentioned algorithms only work above the smoothing parameter of the lattice because they incur error that depends on how smooth the distribution is. Recently, @cite_3 showed that the averages of pairs of vectors sampled from the centered discrete Gaussian will be distributed as discrete Gaussians with a lower parameter, as long as we condition on the averages lying in the lattice. They then showed how to choose such pairs efficiently and proved that this is sufficient to sample from any centered discrete Gaussian in @math time---even for parameters @math below smoothing. @cite_30 then extended this idea to arbitrary Gaussians (as opposed to just centered Gaussians) with very low parameters @math . In both cases, the sampler actually outputs exponentially many vectors from the desired distribution.
@cite_30 @cite_3
1624710162 2951200405
We give a 2 n+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 a#x007E; O (4n)-time and a#x007E; 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 due to Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS) 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 ADRS, the analysis uses substantial new ideas. This yields a 2n+o(n)-time algorithm for approximate CVP with the very good approximation factor a#x03B3; = 1+2-o(n log n). Second, we show that the approximate closest vectors to a target vector can be grouped into "lower-dimensional 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. We give a randomized @math -time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic @math -time and @math -space algorithm of Micciancio and Voulgaris (STOC 2010, SIAM J. Comp. 2013). In fact, we give a conceptually simple algorithm that solves the (in our opinion, even more interesting) problem of discrete Gaussian sampling (DGS). More specifically, we show how to sample @math vectors from the discrete Gaussian distribution at any parameter in @math time and space. (Prior work only solved DGS for very large parameters.) Our SVP result then follows from a natural reduction from SVP to DGS. We also show that our DGS algorithm implies a @math -time algorithm that approximates the Closest Vector Problem to within a factor of @math . In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate @math discrete Gaussian samples in just @math time and space. Among other things, this implies a @math -time and space algorithm for @math -approximate decision SVP.