LWE and distributions

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?

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.

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.