1
$\begingroup$

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$ ?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Mark
    Apr 15 at 16:33
  • $\begingroup$ 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. $\endgroup$
    – 2646jiaxing
    Apr 16 at 5:45
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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}$ ? $\endgroup$
    – 2646jiaxing
    Apr 23 at 8:30
  • $\begingroup$ 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}$. $\endgroup$
    – 2646jiaxing
    Apr 23 at 8:44
  • $\begingroup$ Sampling exactly from $D_{Z,s}$ is critical for trapdoor inversion (such as in the GPV signature scheme) but not for LWE/RLWE. $\endgroup$
    – LeoDucas
    Apr 26 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.