4
$\begingroup$

In LWE, the error term $e$ is "classically" obtained from the discrete normal distribution. Why is it so often found that this distribution is used? Are there other possibilities for distributions?

The secret $s$ is often uniformly distributed, this makes sense, if one wants to "hide" just the secret in the (uniformly distributed) matrix $A$. But would LWE remain safe if $s$ did not result from a uniform distribution?

$\endgroup$
2
  • 3
    $\begingroup$ Relevant answer. There's nothing special about the normal distribution, but apparently it yields tight proofs. And yes it is OK, and even common, to sample $s$ from a Gaussian or uniform binary distribution. $\endgroup$
    – rozbb
    Jul 15, 2023 at 17:06
  • 1
    $\begingroup$ @rozbb binLWE is only about the secret distribution, not the error distribution. LWE with binary errors is insecure due to the Arora-Ge attack. Also, binRLWE is not known to be secure (some people still use it, just there isn't a theoretical basis for this). $\endgroup$
    – Mark Schultz-Wu
    Jul 19, 2023 at 19:27

2 Answers 2

4
$\begingroup$

In (m/r)LWE we care about both correctness (the property that the deciphering process recovers the plaintext with extremely high probability) and security. Correctness is not certain in most LWE schemes, but frequently depends on values $\langle \mathbf s,\mathbf e\rangle$ being less than some fraction of $q$ (typically less than $q/4$) where $\mathbf s$ and $\mathbf e$ have entries drawn from various distributions. Treating the $\langle \mathbf s,\mathbf e\rangle$ terms as sums of a large number random variables (say in the case where entries of $\mathbf s$ are drawn uniformly and the distribution of $\mathbf e$ can be various), proofs/estimates of correctness often approximate this as a normally distributed value per the central limit theorem. This argument holds asymptotically as the dimension increases, but converges more quickly for some distributions. As the sum of two independent normal random variables is normally distributed, convergence is immediate if errors are normally distributed, so that the estimate holds even in low dimensions, the ability to ignore dimensional dependence greatly simplifies proofs and estimates.

The discrete Gaussian distribution can be a pain to sample from in comparison to other distributions. In particular, the binomial distribution can easily be sampled from uniform binary strings using a popcount. The binomial also converges rapidly to the central limit and this has made it a popular choice in systems such as NewHope and Kyber. Other systems use the uniform distribution where the convergence is less rapid, but for the large dimensions in question can be assumed to be close enough. One could perhaps consider other discrete distributions e.g. Poisson, but practically the trade-off is between ease of sampling and tightness of convergence to the central limit.

Likewise, the distribution for $\mathbf s$ can be taken other than uniform if one can produce a good enough argument for the size of $\langle \mathbf s,\mathbf e\rangle$ with high probability for correctness whilst also ensuring that $\mathbf s$ has sufficient minimum entropy to avoid guessing and with overwhelming probability has sufficient size to keep lattice attacks hard.

$\endgroup$
2
  • $\begingroup$ this isn't correct --- $\langle \vec s, \vec e\rangle$ is a $\chi^2_{(n)}$ random variable when $\vec s,\vec e$ are i.i.d. (continuous) Gaussians. In general it will be somewhat different from a Gaussian (it solely has sub-exponential tails rather than sub-Gaussian tails). $\endgroup$
    – Mark Schultz-Wu
    Jul 19, 2023 at 19:24
  • $\begingroup$ @Mark I've tried to limit my discussion to the simpler and more familiar case of central limit convergence. In particular if we consider static $\mathbf s$ and ephemeral, normal $\mathbf e$ then the analysis holds. $\endgroup$
    – Daniel S
    Jul 19, 2023 at 19:32
2
$\begingroup$

It is worth mentioning there are two answers to this depending on whether you are working with things like

  • encryption, where everything is easy, or
  • signatures, where it is less easy.

Encryption:

For encryption, most people practically think at this point that the particular distribution you sample $e$ from doesn't matter, provided it is high-enough entropy. Common distributions are things like

  1. discrete Gaussians. These are the maximum entropy distribution on $\mathbb{Z}$ for given (fixed) mean and variance, i.e. are somewhat natural from this entropy point of view,
  2. uniform distributions --- especially of the form $[-2^k+1,\dots, 2^k]$ are extremely simple to sample from, it simply requires $k+1$ uniform bits
  3. binomial distributions: if you sample $k+1$ bits and add them (and recenter to be around 0), you'll get a more concentrated distribution (= correct for smaller ciphertext modulus $q$) that is still reasonably high entropy

there are plenty of other things you can do though. It doesn't matter too much, as long as the support of the error distribution isn't too small (where things like the Arora-Ge attack start becoming an issue).

Signatures:

For signatures, things can matter quite a bit more. This is because often you end up in a situation where you have some random quantity $r$ that is distributed according to a distribution that depends on the secret key (for example $r\sim \mathcal{D}_{\mathsf{sk}, \sigma^2}$, or something). If an adversary gets enough samples of the $r$, they can plausibly reconstruct the secret key, which is bad.

This can be fixed in a variety of ways. A very common one is known as "rejection sampling". You again

  1. generate $r\sim\mathcal{D}_{\mathsf{sk}, \sigma^2}$, and
  2. "reject" $r$ (i.e. regenerate an independent value $r'$) subject to some condition $\mathsf{Cond}(r)$.

The condition is chosen such that that the distribution $\mathcal{D}_{\mathsf{sk}, \sigma^2}\mid \mathsf{Cond}(r)$ is independent of the secret key, i.e. has no issues with leakage.

In this setting, Gaussians often perform better on a variety of metrics, for example

  1. shortness (which leads to smaller parameters of the schemes), and
  2. probability that $\mathsf{Cond}(r)$ occurs (so you have to generate less signatures to find one that "passes")

That being said, they are not obviously optimal. In practice, rejection sampling (where the target distribution is Gaussian) seems to require computing transcedental functions to relatively high precision, which can be bad in practice (less efficient, requires precomputed constants for the transcedental functions, hard to make side-channel secure). For this reason, the signature scheme Dilithium chose the target distribution to be uniform on a box. There is a new signature scheme in NIST's "round 4" contest that chooses it to be uniform over a sphere (HAETAE). In both cases, Gaussians are practically not used, though theoretically there are larger gains to be had here than in the case of (standard) encryption.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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