24
$\begingroup$

The Wikipedia article on RWE 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 guarenteeing they will be small. However, the articles mentions that the 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 preferably - 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 of 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 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 intution 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.

https://en.wikipedia.org/wiki/Ring_learning_with_errors_key_exchange

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Aug 16 '17 at 2:50
  • $\begingroup$ Gaussian sampling was found to be vulnerable, for reasons given by Stephen Galbraith a few years back, and also covered by Peter Schwabe at PQCrypto '17 summer school session (Lattice Based Crypto IV, 8 minutes in). videos.2017.pqcrypto.org/school $\endgroup$ – nonce Aug 19 '17 at 3:42
  • $\begingroup$ Apologies, it's 30 minutes into the Lattice IV talk when it shifts to New Hope - Simple. $\endgroup$ – nonce Aug 19 '17 at 3:58
  • $\begingroup$ Seems like it's already been answered, although I'm not sure if it specifically fits your exact uncertainty: crypto.stackexchange.com/questions/32624/… You can always say "because math" and be done with it. $\endgroup$ – Daniel B Jun 9 '18 at 18:46
  • $\begingroup$ I answered this question in another post: crypto.stackexchange.com/questions/59903/… Basically, Gaussian error distribution is more uniform than what you think of as the "uniform" distribution, is easier to implement in a lattice-independent way, and is easier to prove things about. $\endgroup$ – djao Jun 10 '18 at 13:06
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 - I suppose if sampling issues were not a problem, everyone would use Gaussians for their optimal trade-off between size and entropy. Alternatives are mostly studied exactly because of these sampling issues. $\endgroup$ – TMM Dec 31 '18 at 15:09
  • $\begingroup$ This is also my understanding. In addition, there are some situations where we still don't know how to remove Gaussians (except at the cost of a huge overhead in performances): trapdoor sampling (introduced in eprint.iacr.org/2007/432), which is used in hash-then-sign schemes, identity-based encryption schemes, etc. It is not directly relevant to the question, but still worth mentioning IMHO. $\endgroup$ – Thomas Prest Jan 2 at 16:27
-1
$\begingroup$

Superficial explanation: Gaussian distribution arises in worst-case (of well-known lattice problem, e.g. Closest Vector Problem) to average-case (of RLWE problem) reduction. Because this reduction (worst-case to average-case) is not trivial, it involves different distributions. This is why distributions matter.

I'm afraid to make a mistake, but seems like Gaussian distribution doesn't prevent any known attacks on RLWE-based schemes. It's just a thing which gives you ProvSec. At least, I saw this opinion(regarding pNE, provable-secure variant of NTRUEncrypt) in work of Daniel Bernstein et al. - https://ntruprime.cr.yp.to/nist/ntruprime-20171130.pdf

$\endgroup$
  • $\begingroup$ Gaussians appear in multiple contexts as a good choice, not just for provable security. (Your answer suggests that if you don't care about provable security reductions there is no reason to use Gaussians, which is false.) $\endgroup$ – TMM Dec 31 '18 at 15:13

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.