2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$ ? $\endgroup$
    – Bob
    Jun 11, 2021 at 2:19
  • $\begingroup$ 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. $\endgroup$
    – Chris Peikert
    Jun 11, 2021 at 2:22

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.