Discrete Gaussian Sampling Reduces to CVP and SVP
Noah Stephens-Davidowitz · 2015
The discrete Gaussian Dℒ–t,s is the distribution that assigns to each vector x in a shifted lattice ℒ — t probability proportional to . 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 s have found many uses in cryptography and in reductions between lattice problems. And, in the past year, Aggarwal, Dadush, Regev, and Stephens-Davidowitz showed 2n+o(n)-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).