# The error distribution in LWE

$$\textbf{Continuous LWE}$$ : $$(\overrightarrow{a}, b)\in \mathbb{Z}_q^n\times \mathbb{T}$$, where $$\mathbb{T}=\mathbb{R}/\mathbb{Z}$$, $$b = \langle \overrightarrow{a},\overrightarrow{s}\rangle/q + e\mod 1$$, where the error $$e$$ is sampled from $$\Psi_\alpha(x) := \sum_{k=-\infty}^{\infty}\frac{1}{\alpha}\cdot exp(-\pi(\frac{x-k}{\alpha})^2), x\in [0,1)$$ over the torus $$\mathbb{T}$$. The density function $$\Psi_\alpha$$ is just the Guassian function $$\rho_\alpha(x) = \frac{1}{\alpha}exp(-\pi x^2/\alpha^2) \mod 1$$.

$$\textbf{The discretization}:$$ transform the continuous sample $$(\overrightarrow{a},b)$$ to $$(\overrightarrow{a}, \lfloor qb\rceil) \in \mathbb{Z}_q^{n+1}$$, the $$\lfloor qb\rceil = \langle \overrightarrow{a},\overrightarrow{s}\rangle + \lfloor qe \rceil \mod q$$, therefore, the error in discretization is the distribution $$q\cdot\Psi_\alpha$$ over $$\mathbb{Z}_q$$.

$$\textbf{The rounded Gaussian}:$$ $$\rho_\alpha(x) = \frac{1}{\alpha}exp(-\pi x^2/\alpha^2)$$ which is the Gaussian distribution over $$\mathbb{R}$$, we transform it to $$\mathbb{Z}_q$$ by $$\lfloor \rho_\alpha \rceil \mod q$$, which means that we sample a real from $$\rho_\alpha$$, then round it to integer and modulo $$q$$, then $$\lfloor \rho_\alpha \rceil \mod q$$ is also a distribution over $$\mathbb{Z}_q$$..

$$\textbf{My Question}:$$

1. Are the distribution in discretization $$q\cdot \Psi_\alpha$$ and the rounded Gaussian $$\lfloor \rho_\alpha \rceil \mod q$$ over $$\mathbb{Z}_q$$ the same?

2. If we choose the $$\lfloor \rho_\alpha \rceil \mod q$$ or $$\lfloor q\cdot \Psi_\alpha\rceil$$ as the error distribution in discretization LWE, is it still hard?

I think the two distribution over $$\mathbb{Z}_q$$ are different. The $$\lfloor q\cdot \Psi_\alpha\rceil$$ is just the distribution in [Regev05] which has been proved hard. Then, how about the $$\lfloor \rho_\alpha \rceil \mod q$$ ?

The distributions are the same. That is, rounding and modding (by any integer $$q$$) essentially commute: $$\lfloor \rho_a \rceil \bmod q = \lfloor \rho_a \bmod q \rceil$$, where on the right we are rounding $$\mathbb{R}/q\mathbb{Z}$$ to the closest element of $$\mathbb{Z}/q\mathbb{Z}$$ (so the result remains modulo $$q$$). This follows simply from the fact that $$\lfloor x \rceil +kq =\lfloor x +kq \rceil$$ for any integer $$k$$. So, for any $$v \in \mathbb{Z}/q\mathbb{Z}$$ its probability is the same under the two distributions.
• Thank you for your answer. I've tried to derive that: If the density function of $e$ is $\Psi_\alpha$, then density function of $qe$ is $\frac{1}{q}\Psi_\alpha(\frac{y}{q})=\sum_{k=-\infty}^{\infty}\frac{1}{\alpha q} exp(-\pi \frac{(y-kq)^2}{(\alpha q)^2})$, it should be a Gaussian distribution with parameter $\alpha q$, but for the $\rho_\alpha \mod q$, its parameter seems to be $\alpha$, not $\alpha q$. So I guess what you mean is the $qe$ is the same as $\rho_{\alpha q} \mod q$ ?
• Of course, you need to scale both $\Psi_\alpha$ and $\rho_\alpha$ by the same $q$ factor, or they obviously won’t match. Then, the rounding commutes with the modding. Jun 11, 2021 at 2:22