Faster discrete Gaussian sampling

Question

Our goal is find a faster discrete Gaussian sampling to solve $"SVP"$ problem in lattice:

A lattice is discrete subgroup of $R^n$ such that define as below:

let $\{b_1,\cdots ,b_n\}$ be a basis in $R^n$. Then $L:=\{a_1b_1+\cdots+a_nb_n | a_i \in Z\}$ is a lattice.

Shortest vector problem in $L$ is:

$SVP(L)$ = shortest non-zero $y\in L$.

This is a $NP-hard$ problem to solve. The best algorithm to improve approximation of this problem mentioned by "Discrete Gaussian Sampling". In this method, the TIME and SPACE computed $2^{n+ o(n)}$. What is the faster discrete Gaussian sampling?

Answer 1

Asymptotically, the fastest provable algorithm for SVP is based on discrete Gaussian sampling, achieving both time and space complexity $2^{n + o(n)}$ in dimension $n$. This algorithm finds a way to obtain samples from a discrete Gaussian on the lattice with a very narrow standard deviation, so that most of the probability mass is concentrated on short lattice vectors, and the probability mass on shortest vectors is sufficiently large that $2^{n + o(n)}$ samples from this distrubition suffice to find one shortest vector. The time to generate even a single sample from such a discrete Gaussian with small standard deviation is however already $2^{n + o(n)}$.

As for algorithms for "discrete Gaussian sampling", there are two different topics to consider here:

• A discrete Gaussian with a large standard deviation is very "flat", has a lot of probability mass concentrated around vectors with huge norms, and therefore it turns out to be quite easy to sample from these distributions by first running LLL reduction and then running some polynomial-time sampling algorithm. These discrete Gaussians are commonly used in lattice-based cryptography, e.g. to sample a noise vector in Learning With Errors.
• A discrete Gaussian with a small standard deviation is very narrow, has most of the mass concentrated around short lattice vectors, and therefore accurately sampling from these distributions (without some kind of trapdoor information about the lattice) is known to be hard.

What defines "small" and "large" above is related to what is commonly called the "smoothing parameter" (see e.g. here). Sampling "above smoothing" is usually considered "easy" while sampling "below smoothing" is "hard", if you have say an LLL-reduced basis of a lattice.

Note that in "practice", the DGS algorithm for SVP is much worse than enumeration-based approaches (see e.g. here), lattice sieving algorithms (see e.g. here), and BKZ-enumeration hybrids like random sampling reduction. Heuristics for instance suggest you can solve SVP in time and space less than $2^{0.3n + o(n)}$ with sieving, and in practice sieving has been used to solve SVP challenges in dimensions as high as 155.