Where the Noise Comes From

The definition of an LWE sample left one thing unspecified. It said the error $e$ is drawn from a distribution $\chi$ concentrated near zero, without saying which. That choice is a real design decision, and the standards made one that a mathematician would not have made first.

01.Two requirements pulling apart

The error has to satisfy two things at once, and they conflict.

It must be large enough that the noise genuinely destroys linear algebra. The demonstration used errors of magnitude at most $1$ and that sufficed at $q = 17$, but the relevant quantity is the error size relative to $q$. If the error were always $0$, the scheme would be plain linear algebra and trivially broken.

It must be small enough that the legitimate recipient can still decrypt. The honest party has a trapdoor that recovers the message provided the accumulated noise stays below some threshold. Push past it and decryption fails for everybody, sender and receiver alike.

So the distribution is chosen to sit in a band. Both boundaries are real, and the second one is the reason lattice schemes have a non-zero decryption failure probability, a concept with no analogue in RSA.

02.The discrete Gaussian

The mathematically natural choice is the discrete Gaussian, written $D_{\mathbb{Z}, \sigma}$, which puts probability on each integer $x$ proportional to

$$\exp\!\left( \frac{-x^2}{2\sigma^2} \right).$$

This is the familiar bell curve, sampled at whole numbers rather than over a continuum. The parameter $\sigma$ is the standard deviation, controlling how wide the bell is.

Gaussians are the natural choice because they behave beautifully under the operations that security proofs need. The sum of two Gaussians is a Gaussian. Their Fourier transform is a Gaussian. Regev's worst-case reduction from The Learning With Errors Problem is proved with Gaussian noise, and the proof leans on those properties.

So the theory wants Gaussians.

03.Why the standards do not use them

Sampling a discrete Gaussian exactly is awkward, and the awkwardness is a security problem rather than an inconvenience.

The usual methods are rejection sampling, where you draw a candidate and sometimes throw it away and try again, or a lookup table of cumulative probabilities. Both have a property that is fatal here: the time they take depends on the value they produce.

Rejection sampling loops a variable number of times. A table lookup touches a memory address determined by the sample, which lands in the processor cache or does not.

Either way, an attacker measuring how long the sampler took, or which cache lines it touched, learns something about the error value. The error is what hides the secret. Leaking it leaks the key.

These are side-channel attacks, and they are not hypothetical. Gaussian samplers in lattice implementations have been a productive source of published attacks for over a decade, including against real deployed code. The mathematics was fine every time. The implementation leaked.

04.The centred binomial distribution

The standards use a different distribution, chosen because it can be sampled in constant time by construction.

A centred binomial sample with parameter $\eta$ is

$$X \;=\; \sum_{i=1}^{\eta} (a_i - b_i),$$

where all $a_i$ and $b_i$ are independent uniform bits, each $0$ or $1$.

Work the smallest case by hand. With $\eta = 2$, draw four bits, say $a = (1, 0)$ and $b = (1, 1)$. Then

$$X \;=\; (1 - 1) + (0 - 1) \;=\; 0 + (-1) \;=\; -1 .$$

The output lies in $\{-\eta, \ldots, +\eta\}$, it is centred at zero by symmetry, and its variance is $\eta/2$. For $\eta = 2$ the possible values are $-2, -1, 0, 1, 2$, with probabilities $1/16$, $4/16$, $6/16$, $4/16$, $1/16$. That is a bell shape, coarse but recognisable.

Here is the implementation trick that makes it worth using. Take two $\eta$-bit strings $a$ and $b$, and note that

$$X \;=\; \operatorname{popcount}(a) \;-\; \operatorname{popcount}(b),$$

where $\operatorname{popcount}$ counts the one-bits. Population count is a single instruction on every modern processor and a small tree of adders in hardware.

That gives the three properties the Gaussian could not.

Cheap. Two popcounts and a subtraction. No loop, no table.

Constant time by construction. There is no rejection, no data-dependent branch, and no data-dependent memory access. The sampler takes the same time and touches the same addresses regardless of what it produces. The side channel is not mitigated, it is absent.

Narrow range. For $\eta \in \{2, 3\}$, which is what ML-KEM uses, the sample fits in three signed bits. Every arithmetic step downstream stays in narrow precision, which matters for both software vectorisation and hardware area.

05.What it costs

Substituting a centred binomial for a Gaussian is not free, and the trade is understood.

For a fixed variance the two distributions give essentially the same cryptographic hardness, and NIST accepted the substitution in both FIPS 203 and FIPS 204. But the centred binomial is not a Gaussian, so Regev's reduction does not apply to it verbatim. The security argument for the deployed schemes is therefore a little less tidy than the theory would be with exact Gaussians.

The centred binomial also has slightly heavier behaviour at its extremes for a given variance, which raises the decryption failure probability a little. The response is to choose parameters with margin, so that the failure probability stays far below any level an attacker could exploit.

That trade, a small loss in proof tidiness and failure margin in exchange for the complete elimination of a side channel, is a fair summary of how the standards were designed throughout. This is the first place in the book where an implementation concern has visibly changed the mathematics, and it will not be the last. Chapter 7 is entirely about that boundary.