5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As an example, I suggest reading up on LWE. The error introduced is typically sampled from a discrete distribution that approximates a Gaussian. This error is what makes the problem difficult without knowledge of the key, and allows use as a cryptographic primitive. You could probably use a different distribution, but this would almost certainly be less efficient. $\endgroup$ – bkjvbx Jun 9 '18 at 15:56
9
$\begingroup$

A Gaussian distribution satisfies the following desirable properties:

  • It can be implemented coordinate-wise: If $x_1, x_2, \ldots , x_n$ are each sampled from a one-variable Gaussian distribution, then $(x_1,x_2,\ldots,x_n)$ is sampled from a multivariable Gaussian distribution.
  • It approximates a uniform error distribution modulo a lattice exponentially well, regardless of what the lattice is.

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:

Gaussian 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:

normal distribution modulo 1

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$:

normal distribution

If we graph the fractional part of this distribution, we get:

normal distribution modulo 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.