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.