# Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?

Let $$\rho_s(x) = e^{-\pi x^2/s^2}$$ be the Gaussian measures, then the discrete Gaussian distribution on $$\mathbb{Z}$$ could be defined as $$D_{\mathbb{Z},s}(x) = \rho_s(x)/\sum_{n\in \mathbb{Z}}\rho_s(n)$$.

In [Regev05], the distribution $$\Psi_s(r)$$ on torus $$\mathbb{T}=\mathbb{R}/\mathbb{Z}$$ is defined :

$$\Psi_s(r)=\sum_{k=-\infty}^{+\infty}\frac1s\cdot exp\left(-\pi \left(\frac{r-k}{s}\right)^2 \right), r\in \mathbb{T}$$

then, it can be discretized as a distribution on $$\mathbb{Z}_p$$ :

$$\overline{\Psi}_s(i) = \int_{(i-1/2)/p}^{(i+1/2)/p}\Psi_s(x)dx, \ \ i\in \mathbb{Z}_p$$

What I want to know is: if the $$D_{\mathbb{Z},s} \mod p$$ is the same as the $$\overline{\Psi}_s$$ on $$\mathbb{Z}_p$$ ?

• Doesn't your discritization method "ignore the tails" of $\Psi_s$? In particular I see no reason why the $\overline{\Psi}$ should have total probability 1, especially if one chooses very large $s$ (say $s \gg p$) so a relatively large amount of probability mass will be contained in the tails.
– Mark
Apr 15, 2021 at 16:33
• the $\Psi_s$ is the distribution on torus, it looks like the Gaussian density function mod 1. Because the function $1/s exp(-\pi r^2/s^2)$ is density function on real R, so the $\Psi$ should be a density function on torus T.
– Bob
Apr 16, 2021 at 5:45

There are two ways to discretize: rounding and conditioning.

The first discretization you use to define $$D_{\mathbb Z,s}$$ from $$\rho_s$$ is using conditionning.

The second one defining $$\bar \Psi_s$$ from $$\Psi_s$$ is using rounding (the density at integer $$x$$ of the former distribution is given the total density of the interval $$[x-\frac 1 2, x+ \frac 12]$$ of the latter distribution).

So, because of this, the two distributions are not the same. However, for large $$s$$, they would be very close to each other, because they would both be very close to uniform.

To summarize: the moding (ie going from R to the torus) and discretizing do commute, but only if you use the same discretization on both path.

• Thank you! According to you say, In [Regev05], the author defined the discretized LWE, the error term is the distribution $\overline{\Psi}_s$ on $\mathbb{Z}_p$, so it is just a rounding, not the discrete Gaussian distribution $D_{Z,s}$ ?
– Bob
Apr 23, 2021 at 8:30
• I find many open libraries which implement the LWE or RLWE module, the way they generate the error is just sampling from a continuous Gaussian distribution and then round it to nearest number. But in [GPV08], the author points out that rounding a continuous Gaussian is not the $D_{Z,s}$.
– Bob
Apr 23, 2021 at 8:44
• Sampling exactly from $D_{Z,s}$ is critical for trapdoor inversion (such as in the GPV signature scheme) but not for LWE/RLWE. Apr 26, 2021 at 15:59