一、简介

LWE（Learning With Errors，带误差学习）是一种基于格理论的计算难题，由 Oded Regev 于 2009 年提出，是后量子密码学（PQC）的核心基础之一。

LWE 问题的数学形式是：给定多个带有离散分布误差的近似线性方程，求解隐藏的秘密向量。由于误差会在消元过程中累积，高斯消元法等传统方法无法有效求解。LWE 还衍生出了环学习时出错（Ring-LWE，RLWE）和模组学习时出错（Module-LWE，MLWE）等问题，构成了许多后量子密码算法的理论基础。

为什么格密码能够抵抗量子计算？

Shor 算法能够破解 RSA，关键在于模指数运算具有周期性，而量子傅里叶变换非常擅长寻找周期。格密码的安全性则建立在高维格上的困难几何问题之上，目前没有已知的量子算法能够高效解决这类问题。

二、基本概念

离散高斯分布 $\Psi_\alpha$

离散高斯分布的定义域是一个个孤立的格点。直观地说，可以把连续高斯分布的曲线离散化为一组点，点的高度反映取到对应格点的概率大小。

离散高斯抽样

离散高斯抽样（Discrete Gaussian Sampling）是一种从离散集合中随机选择元素的方法，同时遵循高斯分布的统计特性。它通常用于构建基于格的加密方案和数字签名方案，主要用来生成随机误差项，从而增加密码方案的安全性。

核心参数

  • $n$：格的维度。

  • $q$：模数，需要足够大，以避免误差导致模运算结果产生歧义。例如，Kyber 使用 $q=3329$，Dilithium 使用 $q=8380417$。

  • $\alpha$：噪声参数，控制离散高斯分布的宽度，通常取 $0.01$ 到 $0.05$ 之间。

  • $s$：秘密向量，长度为 $n$，元素均匀采样自 $\mathbb{Z}_q$ 或某个小范围整数集合。

  • $e$：误差向量，长度为 $n$，元素采样自离散高斯分布 $\Psi_\alpha$。

  • $a$：随机向量，长度为 $n$，元素均匀采样自 $\mathbb{Z}_q$。

  • $b$：带误差的线性组合，满足

    $$
    b = \langle a,s\rangle + e \pmod q.
    $$

三、基本公式

单个 LWE 样本

设 $s\in\mathbb{Z}_q^n$ 是秘密向量，$a\in\mathbb{Z}_q^n$ 是公开的随机向量，$e\in\mathbb{Z}_q$ 是小误差。

计算：

$$
b = \langle a,s\rangle + e
= \sum_{i=1}^{n}a_i s_i + e
\pmod q.
$$

此时，一个 LWE 样本可以记为 $(a,b)$。

多个 LWE 样本

收集 $m$ 个样本 $(a_1,b_1),\ldots,(a_m,b_m)$，其中

$$
b_i = \langle a_i,s\rangle + e_i \pmod q.
$$

将这些随机向量按行排列，得到

$$
A =
\begin{pmatrix}
a_1^{\mathsf T} \\
a_2^{\mathsf T} \\
\vdots \\
a_m^{\mathsf T}
\end{pmatrix}
\in \mathbb{Z}_q^{m\times n}.
$$

误差向量和观测向量也可以排列为

$$
e =
\begin{pmatrix}
e_1 \\
e_2 \\
\vdots \\
e_m
\end{pmatrix},
\qquad
b =
\begin{pmatrix}
b_1 \\
b_2 \\
\vdots \\
b_m
\end{pmatrix}.
$$

最终得到矩阵形式

$$
b = As+e \pmod q.
$$

四、LWE 的两类问题

搜索问题（Search-LWE）

  • 输入：大量独立同分布的样本 $(a_i,b_i)$，其中 $b=As+e\pmod q$。
  • 目标：从样本 $(A,b)$ 中恢复秘密向量 $s$。

判定问题（Decision-LWE）

  • 输入：一组样本。

  • 目标：区分样本来自带误差的 LWE 分布，还是来自均匀分布

    $$
    \mathbb{Z}_q^n\times\mathbb{Z}_q.
    $$

如果能够解决搜索 LWE 问题，通常也可以通过归约解决判定 LWE 问题。

五、RLWE 与 MLWE

Ring-LWE

考虑商环

$$
R = \frac{\mathbb{Z}[x]}{x^n+1},
\qquad
R_q = \frac{\mathbb{Z}_q[x]}{x^n+1}.
$$

秘密量、随机量和误差均变为商环中的多项式 $s(x)$、$a(x)$ 和 $e(x)$，满足

$$
s(x),a(x),e(x)\in R_q.
$$

计算

$$
b(x)=a(x)s(x)+e(x)\pmod q.
$$

优点：

RLWE 的代数结构更强，可以用少数几个多项式表示原本规模很大的随机矩阵，因此密钥更小、计算更快；代价是对商环的选择要求更严格。

Module-LWE

使用同一个商环

$$
R = \frac{\mathbb{Z}[x]}{x^n+1},
\qquad
R_q = \frac{\mathbb{Z}_q[x]}{x^n+1}.
$$

秘密量变为多项式向量

$$
s=
\begin{pmatrix}
s_1(x) \\
s_2(x) \\
\vdots \\
s_k(x)
\end{pmatrix}
\in R_q^k.
$$

随机矩阵和误差向量分别满足

$$
A\in R_q^{k\times k},
\qquad
e\in R_q^k.
$$

计算

$$
b=As+e\pmod q.
$$

六、格与 LWE、RLWE

LWE 与 CVP

已知 $A,b$ 并希望恢复 $s$ 时，可以将问题看作一个有界距离解码问题，进而与 CVP 联系起来。令 $k\in\mathbb{Z}^m$，则

$$
b+qk=As+e
\qquad\Longleftrightarrow\qquad
b+qk-As=e.
$$

利用 Kannan 嵌入，可以构造如下格基：

$$
\begin{aligned}
&\left(k^{\mathsf T},s^{\mathsf T},1\right)
\begin{pmatrix}
qI_m & 0_{m\times n} & 0_{m\times 1} \\
-A^{\mathsf T} & I_n & 0_{n\times 1} \\
b^{\mathsf T} & 0_{1\times n} & 1
\end{pmatrix} \\
&\qquad= \left(e^{\mathsf T},s^{\mathsf T},1\right).
\end{aligned}
$$

实际求解时，可以利用 Kannan 嵌入将 CVP 转换为 SVP，再使用 LLL 等格基约化算法寻找短向量。下面是 SageMath 中的示意代码：

1
2
3
4
5
6
7
8
9
10
11
12
# A 为 m×n 矩阵，b 为长度为 m 的向量，q 为模数
I_m = identity_matrix(ZZ, m)
I_n = identity_matrix(ZZ, n)

B = block_matrix(ZZ, [
    [q * I_m, zero_matrix(ZZ, m, n), zero_matrix(ZZ, m, 1)],
    [-A.transpose(), I_n, zero_matrix(ZZ, n, 1)],
    [b.transpose(), zero_matrix(ZZ, 1, n), matrix(ZZ, 1, 1, [1])]
])

B_reduced = B.LLL()
v = B_reduced[0]

RLWE 的系数矩阵表示

设商环中的两个多项式为

$$
g(x)=b_0+b_1x+b_2x^2+\cdots+b_{n-1}x^{n-1},
$$

$$
h(x)=c_0+c_1x+c_2x^2+\cdots+c_{n-1}x^{n-1}.
$$

在进行模多项式约化之前，令

$$
g(x)h(x)=\sum_{i=0}^{2n-2}k_i x^i,
\qquad
k_i=\sum_{r+t=i}b_r c_t.
$$

于是，卷积过程可以写成

$$
\begin{aligned}
&(b_0,b_1,\ldots,b_{n-1})M_L
=(k_0,k_1,\ldots,k_{2n-2}),\\[4pt]
&M_L=\begin{pmatrix}
c_0 & c_1 & \cdots & c_{n-1} & 0 & \cdots & 0 \\
0 & c_0 & \cdots & c_{n-2} & c_{n-1} & \ddots & \vdots \\
\vdots & \ddots & \ddots & \ddots & \ddots & \ddots & 0 \\
0 & \cdots & 0 & c_0 & c_1 & \cdots & c_{n-1}
\end{pmatrix}
\in\mathbb{Z}^{n\times(2n-1)}.
\end{aligned}
$$

由于 $R=\mathbb{Z}[x]/(x^n+1)$，有

$$
x^n=-1,
\qquad
x^{n+j}=-x^j.
$$

因此，若令 $k_{2n-1}=0$，约化后的系数满足

$$
s_j=k_j-k_{n+j},
\qquad 0\leq j\leq n-1.
$$

对应的约化矩阵可以用分块矩阵表示为

$$
M_R=
\begin{pmatrix}
I_{n-1} & 0 \\
0 & 1 \\
-I_{n-1} & 0
\end{pmatrix}
\in\mathbb{Z}^{(2n-1)\times n}.
$$

于是，先进行卷积、再进行商环约化，就得到

$$
(b_0,b_1,\ldots,b_{n-1})M_LM_R
=(s_0,s_1,\ldots,s_{n-1}).
$$

在 SageMath 中，也可以使用商环多项式的 matrix() 方法直接获得乘法矩阵；需要注意具体矩阵的行向量/列向量约定。按照上面的系数向量约定，RLWE 的乘法可以写成

$$
b(x)=A(x)s(x)+e(x)
\qquad\Longrightarrow\qquad
b=sM+e,
$$

其中 $b,s,e$ 分别表示 $b(x),s(x),e(x)$ 的系数向量。

参考资料