Uniform vs discrete Gaussian sampling in Ring learning with errors

Question

The Wikipedia article on RLWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply uniformly selecting the coefficients from the set of small coefficients, thereby guaranteeing they will be small. However, the articles mention that security proofs rely on discrete Gaussian sampling.

However, I have a bit of difficulty wrapping my head around

• Why discrete Gaussian sampling would be better than uniform, security-wise?

I mean, usually uniform is preferable - it maximizes the entropy/information in each sample, making the outcome more unpredictable. I could understand it if the Gaussian sampling technique would somehow serve to avoid (at least with high probability) "weak" parts of the space of outcomes but I have found no information/justification that this is the case.

Another reason I can see why discrete Gaussian might be better is that there is, after all, a chance (albeit a small one) one would select a non-small coefficient, so the space of outcomes is actually larger. However, given that this probability of hitting this extra space is (by design) quite small but also that one would likely immediately reject such a sample (because the algorithm calls for a small polynomial), this seems to be irrelevant.

It is not because I am against discrete Gaussian sampling I just want to understand why it is more secure. Also, I want to understand if it really IS more secure or it is simply easier to prove security in that model. I would actually consider that very interesting if it is the case because it raises the question of why is it easier to prove the security under conditions that are intuitively worse (i.e. discrete Gaussian vs the intuitively better uniform case)? If it is so intuitively clear that uniform sampling is better, surely it must be possible to transform that intuition into a security proof of RWE also under uniform sampling. Otherwise, I would fear the intuition must with high likelihood be wrong or at least dubious.

Answer 1

The TL;DR:

• From a theoretic point of view, Gaussians are the better choice, both for the easiness of the security proof and its optimality in terms of tightness;
• In practice, most of the time you can replace Gaussians by other distributions without too much trouble.

Theory

First, let me elaborate on a few reasons why Gaussians are better in theory:

• When you use an error distribution in LBC, your distribution impacts the scheme in two conflicting ways:

  • Correctness: if the standard deviation of the error distribution is too large, then the correctness of the scheme is not ensured anymore. For example, in the key exchange in your Wikipedia link, if we set the error distribution to be uniform over R_q then the two parties effectively send each other random noise and thus it is impossible for them to agree on a common key with this protocol.
  • Entropy: the entropy of random distributions often play an important role in proving the security of a scheme. This is of course not restricted to lattice-based schemes, but since they are the topic at hand we can for example consider the leftover hash lemma (see this SE post: Relation between decisional SIS and leftover hash lemma in lattices). The SE post considers the error distribution to be over $ \{0,1\}^m$, you can use other distributions as well, but you need them to have sufficient entropy.

  So you are faced with two somewhat conflicting conditions: you need a small standard deviation to ensure correctness, but you require sufficient entropy for the security proof to go through. As it turns out, for a fixed mean and standard deviation, the entropy is maximized for Gaussians. Which is why they look like the best compromise between these conditions.

• While it is not exactly easy to work with Gaussians, they have a few "magical" properties which are handy when doing security proofs: for example, the sum of two Gaussians is a Gaussian. We can't say the same for uniform distributions (of restricted support).

Practice

Generating Gaussian distributions in a fast and secure (against side-channel attacks) way has proven to be difficult, and some methods for doing so have been subjected to devastating side-channel attacks. In addition it can be tedious, so many schemes (but not all) have tried to ditch full-fledged Gaussians without compromising security. For example:

• Approximated Gaussians (using a table and 16 bits of randomness per coefficient sampled) have been considered. See FrodoKEM.
• A popular choice is to rely on centered binomial distributions: they "look like Gaussians", but they can be sampled efficiently and securely (a binomial distribution is a sum of uniform samples in [0,1]). See NewHope and Kyber.
• I have no knowledge of the uniform distribution being used in key exchange, but it is popular in Fiat-Shamir signature schemes which use variants of LWE (see qTESLA, Dilithium).

Funnily, you can even ditch the error distribution entirely and use truncation instead; of course now you no longer rely on the LWE hypothesis but on LWR (Learning with Rounding). This is what Saber does.