I'm reading up on how post-quantum cryptography works, and stumbled upon the notion of discrete Gaussian sampling. However, I can't understand where it fits in the greater picture - currently it feels to me like a solution to a problem nobody put out.
Where exactly in a SVP problem (or any other commonly used lattice problem) would Discrete Gaussian Sampling provide a benefit?
I'm still new to PQ so pardon the highly likely banality of the question
A Gaussian distribution satisfies the following desirable properties:
The first property makes implementation easy, and the second property makes security proofs easy, since many security proofs in lattice-based crypto involve switching around the lattice lots of times until you get what you want.
To show what I mean by the second property, let's consider a one-dimensional lattice $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\} \subset \mathbb{R}^1$. Take a normal distribution with standard deviation $1/2$. In other words, just your average normal distribution:
Suppose that I sample real numbers from this distribution and take the fractional part of the resulting real numbers. (Taking fractional parts correpsonds to taking error vectors with respect to the lattice $\mathbb{Z}$.) The resulting distribution amounts to taking the original normal distribution, chopping it up into unit intervals $\ldots, [-2,-1], [-1,0], [0,1], [1,2], \ldots$, and adding them up. When we do that, we get something quite magical:
Notice how close this distribution is to uniform! The "radius" or standard deviation of this distribution is only $1/2$, which is not much larger than the size of the unit interval; in fact it's smaller. Even with such a small radius, we get a ridiculously good approximation to the uniform distribution. You can prove (and you should prove, as an exercise) that the quality of the approximation is independent of the choice of where the original normal distribution is centered.
Suppose we take a slightly larger normal distribution, say with standard deviation $2/3$:
If we graph the fractional part of this distribution, we get:
That's really really good! You can't even tell that it deviates from uniform. In mathematical terms, we say that the distribution is exponentially close to uniform. Even a small increase in the width of the distribution (from $1/2$ to $2/3$) improves the quality of the approximation dramatically.
You might say, what's the big deal? We can easily get a uniform distribution on any interval. But that's not the point. In lattice-based cryptography, you often don't know what the lattice is. (It's part of someone's secret key.) Suppose as an exercise that we didn't know what this lattice is, and we tried to sample error vectors by taking them uniformly from an interval $[0,n]$ for some $n$. We can't just take the perfect choice of $n=1$. That's cheating, since we're assuming we don't know what the lattice is. In this case, any choice of a small number $n$ will cause the distribution to be horribly wrong; for example, if we chose $n=2/3$ in this scenario, then all of our error vectors would lie in $[0,2/3]$, which is far from uniform in $[0,1]$. Even a slightly larger $n$ is no good; for example if $n=3/2$ then random real numbers sampled uniformly from $[0,3/2]$ will be much more likely to have fractional part (i.e. error vector) lying in $[0,1/2]$ than in $[1/2,1]$. Of course, a very large $n$ (say $n \approx 10^9$) would do the job, but that's exactly the problem: since our distribution on $[0,n]$ doesn't converge to the uniform distribution on $[0,1]$ exponentially fast (unless we cheat by taking $n \in \mathbb{Z}$, which is not allowed), we end up needing to take very large values of $n$, which is not only hard to implement, but a nightmare in security proofs where theoretical analysis is required.
What you need is a way to approximate uniform error vectors exponentially well, without relying on prior knowledge of what the lattice is. Gaussian distributions do that job.
