DI Management Home > Maths > Discrete Gaussian distribution

Discrete Gaussian distribution


In the lattice-based encryption scheme using Learning-With-Errors (LWE), the error or noise vector is created by sampling a Discrete Gaussian Distribution. This page looks at how this works.

Gaussian or normal distribution | Discrete Gaussian distribution | Discrete Gaussian distribution over $\mathbb{Z}_q$ | Discrete Gaussian distribution with width σ = 3.0 | Availability in Sage | Implementation in Python | Rate this page | Contact us

Gaussian or normal distribution

standard deviation
Diagram source: Wikipedia
The probability density function (pdf) of the graph defined by mean $\mu$ and standard deviation $\sigma$ is given by \[ f(x) = \dfrac{1}{\sigma\sqrt{2\pi}}e^{-(x-\mu)^2/2\sigma^2} \] In particular, for $\mu=0$ and $\sigma=1.0$, we have $f(0) = 0.399,\; f(\pm 1)=0.242,\; f(\pm 2)=0.054$. You'll see these values occurring below.
We assume you are familiar with the Gaussian (or normal) distribution over the real numbers. It is defined by two parameters, the mean $\mu$ and the standard deviation $\sigma$. We usually have a centralized distribution with a mean of zero. Samples from a Gaussian distribution should (on the average) obey the 68–95–99.7 rule:
About 68% of values drawn from a normal distribution are within one standard deviation σ away from the mean; about 95% of the values lie within two standard deviations; and about 99.7% are within three standard deviations.
So if we sampled 100 values from a Gaussian distribution with $\sigma = 1.0$, we would have 100 real numbers and would expect approximately 68 of these 100 samples to lie between $-1$ and $+1$, approximately 14 to lie between $+1$ and $+2$, and about 2 to lie between $-2$ and $-3$. You can guarantee with overwhelming odds not to get any values greater than $\pm 6$.

Discrete Gaussian distribution

When we sample a discrete distribution with mean $\mu=0$, the output is a set of integers, centered on zero. This is best explained with a diagram. Here is a histogram plot (shown in blue) of values sampled from a discrete Gaussian distribution with $\sigma=1.0$. The y-axis shows the fraction of the total. The line in red is the probability density function for the Gaussian distribution over the reals.

discrete gaussian s1

Note that the width of one standard deviation is one integer unit. (You may see such a discrete distribution described as having a width of one.) Note that about 40% of the results are equal to zero, about 24% are equal to $+1$ or $-1$, and about 5% are equal to $+2$ or $-2$. Compare these numbers to the blue dots in the diagram over the reals below.

gaussian key values

Discrete Gaussian distribution over $\mathbb{Z}_q$

The effect becomes clearer if we look at the same sample over the finite field $\mathbb{Z}_{31}$

discrete gaussian s1 mod 31

Note how the results bunch up at either end and note the virtually zero probability of values between 4 and 27 ($q-4$).

A typical (sorted) sample of $N=40$ looks like this (not the same numbers as in the diagrams above, but similar)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30]

Discrete Gaussian distribution with width $\sigma=3.0$

For comparison, consider a sample of a discrete Gaussian distribution with width $\sigma=3.0$. With a larger $\sigma$ the curve is flatter, the probability values in the y-axis are reduced by a factor of three, and the width of a standard deviation is three bars of width one.

discrete gaussian s3
discrete gaussian s3 mod 31

Availability in Sage

See DiscreteGaussianDistributionIntegerSampler Discrete Gaussian Samplers over the Integers in the Sage Reference Manual.

import sage.stats.distributions.discrete_gaussian_integer as dgi
def sample_noise(N, R):
   D = dgi.DiscreteGaussianDistributionIntegerSampler(sigma=1.0)
   return vector([R(D()) for i in range(N)])
R = Integers(q)
e = sample_noise(N, R)

Implementation in Python

discrete_gaussian_zq.py Library source code
import discrete_gaussian_zq as Dgi
dgi = Dgi(q)
e = [dgi.D() for x in range(N)]

Example in field $\mathbb{Z}_{31}$

dgi = Dgi(31)
e1 = [dgi.D() for x in range(40)]
print("e1 =", e1)
e1 = [1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 30, 1, 0, 30, 1, 0, 1, 0, 1, 29, 30, 30, 0, 30, 30, 0, 1, 1, 30, 30, 0, 30, 2, 30, 30, 0, 30, 0, 0, 2]

Rate this page

Contact us

To contact us or comment on this page, please send us a message.

This page first published 25 February 2024. Last updated 26 February 2024