The discrete Gaussian distribution $D_{\mathcal{L}, r}(x)$ is defined over a lattice $\mathcal{L}$ with parameter $r$ such that the probability of sampling a lattice vector $x \in \mathcal{L}$ is proportional to its weight
$$
w(x) = e^{-\pi \|x\|^2 / r^2}
$$
where $r$ is the Gaussian parameter, ensures that vectors closer to the origin are more likely to be chosen, which is crucial for many lattice-based cryptographic constructions.

We see that :
- smaller length of vector $x$ is more likely to be sampled.
- smaller parameter $r$ means the distribution is more concentrated around the origin, making shorter vectors more likely to be sampled.
Iteration of Discrete Gaussian Sampling
Given :
-
A lattice $\mathcal{L}(B)$ defined by a basis $B$, and its dual lattice $\mathcal{L}^*(B^{-T})$. They satisfy :
$$
\langle x, y \rangle \in \mathbb{Z} \quad \forall x \in \mathcal{L}(B), y \in \mathcal{L}^*(B^{-T}).
$$
-
Discrete Gaussian distribution $D_{\mathcal{L}, r}(x)$ with parameter $r$ over the lattice $\mathcal{L}(B)$, which defines the probability of sampling each lattice vector $x \in \mathcal{L}(B)$ proportional to its weight
$$
w(x) = e^{-\pi \|x\|^2 / r^2}.
$$
By this distribution, we sample a lattice vector
$$
v \leftarrow D_{\mathcal{L}, r}(x)
$$
-
Target $y \in \mathbb{R}^n$, which is sufficiently close to the dual lattice $\mathcal{L}^*(B^{-T})$.
-
An LWE oracle $\mathcal{O}$.
We aim to find the closest lattice vector $x \in \mathcal{L}^*$ to the target vector $y$, leveraging the discrete Gaussian samples and the LWE oracle $\mathcal{O}$.
Construct LWE Instance
Firstly, We will focus on how to construct a valid LWE instance from the discrete Gaussian samples and the target vector $y$ :
-
Sample a lattice vector $v$ from the discrete Gaussian distribution over the lattice $\mathcal{L}(B)$ with width parameter $r$:
$$
v \leftarrow D_{\mathcal{L}, r}(x)
$$
-
Recover the modularized scalar vector $a = u \pmod q$ from $v$ :
$$
a = B^{-1} v \pmod q
$$
, it serves as the LWE instance’s public vector component.
-
Sample a noise $g \in \mathbb{R}$ from the continuous Gaussian distribution with $0$ mean and standard deviation $\frac{\alpha}{2\sqrt{\pi}}$ :
$$
g \leftarrow \mathcal{D}(0, \frac{\alpha}{2\sqrt{\pi}})
$$
-
Compute the LWE response $b$ using the target vector $y$, the discrete Gaussian sample $v$, and the noise $g$:
$$
b = \langle y, v \rangle / q + g \pmod 1
$$
Explanation of the response vector
Since $y = x + h$ where $x$ is the closest lattice vector to $y$ in $\mathcal{L}^*$ and $h$ is the displacement between $x$ and $y$, we have :
$$
\begin{aligned}
b &= \langle y, v \rangle / q + g \pmod 1 \\
&= \langle x + h, v \rangle / q + g \pmod 1 \\
&= \langle x, v \rangle / q + \langle h, v \rangle / q + g \pmod 1
\end{aligned}
$$
Since $x \in \mathcal{L}^*$ and $v \in \mathcal{L}$, where $x = B^{-T} c, s = c \pmod q$ for some $c \in \mathbb{Z}^n$ and $v = B u, a = u \pmod q$ for some $u \in \mathbb{Z}^n$, we have
$$
\langle x, v \rangle = \langle B^{-T} c, B u \rangle = \langle c, B^{-1} B u \rangle = \langle c, u \rangle \in \mathbb{Z}.
$$
We notice that $c$ and $u$ are the scalar vectors of lattice vectors $x$ and $v$ respectively. And since
$$
\langle c, u \rangle \pmod q = \langle s, a \rangle \pmod q
$$
, thus
$$
\langle c, u \rangle / q \pmod 1 = \langle s, a \rangle / q \pmod 1
$$
Therefore,
$$
b = \langle s, a \rangle /q + \boxed{\langle h, v \rangle / q + g} \pmod 1
$$
where $e = \langle h, v \rangle / q + g$ represents the effective noise in the LWE response, it should also comes from a fixed Gaussian distribution which is independent of $v$ we sampled.
The pair $(a, b)$ is an LWE instance with secret $s$ and effective noise $e = \langle h, v \rangle / q + g$, where $a$ is the public vector component and $b$ is the response vector. In order to ensure $(a, b)$ is a valid LWE instance :
Continue reading →