Score:2

The error distribution in LWE

cn flag
Bob

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

Score:2
in flag

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.

Bob avatar
cn flag
Bob
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$ ?
Chris Peikert avatar
in flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.