Discrete Gaussian Sampling on Lattices, Explained

A discrete Gaussian assigns higher probability to lattice points near a chosen center and lower probability to distant points. Unlike a continuous bell curve, it can only output points in a discrete set such as the integers or a lattice. This distinction matters in cryptography: the output must satisfy an exact algebraic relation while hiding which short basis, if any, helped produce it.

The distribution

For a lattice $\Lambda$ , center $c$ , and positive width $s$ , give each point $x\in\Lambda$ an unnormalized weight $\rho_{s,c}(x)=\exp(-\pi\|x-c\|^2/s^2)$ . Divide by the sum of all weights to obtain probabilities:

D_{\Lambda,s,c}(x)=\frac{e^{-\pi\|x-c\|^2/s^2}}{\sum_{y\in\Lambda}e^{-\pi\|y-c\|^2/s^2}}

The parameter $s$ controls spread: larger values assign meaningful probability to more distant points. It is not the standard deviation. Under this convention, the corresponding continuous Gaussian has per-coordinate standard deviation $s/\sqrt{2\pi}$ . Papers sometimes use a different parameter convention, so compare formulas before comparing quoted widths.

A numerical example on the integers

Set $\Lambda=\mathbb{Z}$ , $c=0$ , and $s=1$ . The point 0 has weight 1; each of −1 and 1 has weight $e^{-\pi}\approx0.0432$ ; each of −2 and 2 has weight $e^{-4\pi}\approx0.0000035$ . The normalizing sum is approximately 1.0864. Therefore 0 is sampled about 92.0% of the time, and each of −1 and 1 about 4.0% of the time. Those probabilities are approximate because the denominator includes every integer, including farther points with tiny weights.

What changes when s grows?

The weight at 1 becomes $e^{-\pi/4}$ when $s=2$ , much larger than at $s=1$ . The distribution spreads across more integers. The center still has the largest weight, but it no longer dominates as strongly.

Why sample over a lattice?

In some lattice signature constructions, a valid response must lie in a particular lattice coset and be short. Choosing any convenient short point can reveal information about a secret basis after many signatures. Gaussian sampling can make the response distribution depend chiefly on the public coset rather than on the particular short basis used to find it, provided the scheme's parameter and sampling conditions hold. This is a key idea in the Gentry–Peikert–Vaikuntanathan trapdoor framework. It is a statement about a proved construction under its assumptions, not permission to replace a specified signature sampler with a generic Gaussian routine.

Gaussian distributions also occur in hardness reductions for LWE. Those are mathematical distributions in proofs; they do not imply every deployed lattice scheme uses a Gaussian sampler. For example, the ML-KEM standard specifies a centered binomial distribution for its small coefficients. The distribution and the implementation requirements must be taken from the actual scheme specification.

How does the smoothing parameter fit in?

The smoothing parameter is a scale at which Gaussian mass on nonzero points of the dual lattice becomes small. Above an appropriate scale, certain distributions modulo the lattice become close to uniform. This is a useful technical condition in security proofs. It does not say that one can simply draw a continuous Gaussian and round each coordinate independently to obtain the exact lattice Gaussian for an arbitrary skewed lattice.

Sampling exactly or within a proved statistical distance can require specialized algorithms. In a real cryptographic implementation, the random-number source, timing behavior, and distribution error all matter. The right implementation is the one required and analyzed by the chosen scheme, not a textbook sketch of the bell curve.

6.3 Discrete Gaussian sampling