LWE中的误差分布

Question

\textbf{Continuous LWE}：(\overrightarrow{a}, b)\in \mathbb{Z}_q^n\times \mathbb{T}，\mathbb{T}=\mathbb{R}/\mathbb{Z}，b = \langle \overrightarrow{a},\overrightarrow{s}\rangle/q + e\mod 1，误差e是在圆环\mathbb{T}上从\Psi_\alpha(x) := \sum_{k=-\infty}^{\infty}\frac{1}{\alpha}\cdot exp(-\pi(\frac{x-k}{\alpha})^2), x\in [0,1)中抽取的。密度函数\Psi_\alpha就是Guassian函数\rho_\alpha(x) = \frac{1}{\alpha}exp(-\pi x^2/\alpha^2) \mod 1。

\textbf{The discretization}: 将连续样本(\overrightarrow{a},b)转换为(\overrightarrow{a}, \lfloor qb\rceil) \in \mathbb{Z}_q^{n+1} ，\lfloor qb\rceil = \langle \overrightarrow{a},\overrightarrow{s}\rangle + \lfloor qe \rceil \mod q，因此，离散化的误差是\mathbb{Z}_q上的分布q\cdot\Psi_\alpha。

\textbf{The rounded Gaussian}: \rho_\alpha(x) = \frac{1}{\alpha}exp(-\pi x^2/\alpha^2)是\mathbb{R}上的高斯分布，我们通过\lfloor \rho_\alpha \rceil \mod q将其转化为\mathbb{Z}_q，这意味着我们从\rho_\alpha中抽取一个实数，然后把它四舍五入为整数和模q，然后\lfloor \rho_\alpha \rceil \mod q也是\mathbb{Z}_q上的一个分布。

\textbf{My Question}:

1. 离散化q\cdot \Psi_\alpha中的分布与\mathbb{Z}_q上的圆形高斯\lfloor \rho_\alpha \rceil \mod q分布相同吗？
2. 如果我们选择\lfloor \rho_\alpha \rceil \mod q或\lfloor q\cdot \Psi_\alpha\rceil 作为离散LWE中的误差分布，它仍然困难吗？

我认为\mathbb{Z}_q上的两种分布是不同的。\lfloor q\cdot \Psi_\alpha\rceil 只是Regev05中的分布，这已经被证明是很难的。那么，\lfloor \rho_\alpha \rceil \mod q呢？

Answer 1

分布是一样的。也就是说，舍入和调制(通过任何整数q)本质上是通勤：\lfloor \rho_a \rceil \bmod q = \lfloor \rho_a \bmod q \rceil，在这里，我们将\mathbb{R}/q\mathbb{Z}舍入到\mathbb{Z}/q\mathbb{Z}的最接近的元素(因此结果仍然是模q)。这很简单地源于\lfloor x \rceil +kq =\lfloor x +kq \rceil对于任何整数k。因此，对于任何一个v \in \mathbb{Z}/q\mathbb{Z}，在这两个分布下，它的概率是相同的。