# 14 LWE 问题与带噪线性方程

整理日期：2026-10-16。  
前置笔记：[09 高斯函数与离散高斯分布](/knowledge/gaussian-functions-and-discrete-gaussians/)、[12 q 元格与模线性方程](/knowledge/q-ary-lattices/)、[13 SIS 问题与短整数关系](/knowledge/sis-and-short-integer-relations/)。

本文采用整数误差形式，向量按列排列，长度使用欧氏范数。

## 1. 从带噪方程到 LWE 样本

**带误差学习问题**（Learning with Errors，LWE）研究从带有随机误差的模线性方程中恢复秘密，或识别这些方程的分布。

设 $q\ge2$，秘密为

$$
s\in\mathbb Z_q^n,
$$

误差分布 $\chi$ 定义在 $\mathbb Z$ 上，通常集中在 $0$ 附近。

固定秘密 $s$ 后，一个 LWE 样本按以下方式生成：

$$
a\leftarrow U(\mathbb Z_q^n),
\qquad
e\leftarrow\chi,
\qquad
\boxed{b=\langle a,s\rangle+e\bmod q.}
$$

公开的是 $(a,b)$，秘密 $s$ 和误差 $e$ 不公开。部分文献直接将误差分布定义在 $\mathbb Z_q$ 上，对应这里的整数误差取模后的分布。样本定义见 [Regev《The Learning with Errors Problem》，CCC 2010，§1，PDF 第 2 页](https://cims.nyu.edu/~regev/papers/lwesurvey.pdf)。

将 $m$ 个样本合并，记

$$
A=(a_1,\ldots,a_m)\in\mathbb Z_q^{n\times m},
\qquad
e=(e_1,\ldots,e_m)^{\mathsf T},
$$

便得到

$$
\boxed{
b=A^{\mathsf T}s+e\bmod q.
}
$$

这里 $n$ 是秘密的维数，$m$ 是样本数。**所有样本共享同一个秘密；各个 $a_i$ 和 $e_i$ 独立抽取。**

本文采用均匀秘密版本：每个实例开始时抽取一次 $s\leftarrow U(\mathbb Z_q^n)$，随后固定它生成全部样本。矩阵形式及随机实例的构造见 [Micciancio《Random Lattices and Lattice-Based Cryptography》，Fall 2019，PDF 第 1 页，Definition 2 及其后的分布说明](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/Lec4-Random.pdf)。

## 2. 噪声的作用与尺度

如果 $e=0$，且 $q$ 为素数、$A$ 满行秩，那么

$$
A^{\mathsf T}s=b
$$

可以通过有限域上的线性消元唯一求解。

加入未知误差后，对方程作线性组合时，误差也随之组合。模 $q$ 上的可逆变换一般不保持整数误差的短性，因此直接消元不再自动恢复秘密。

“小误差”描述的是取模前的整数大小。例如，模 $q$ 的剩余类 $q-1$ 可以来自误差 $-1$。

一个常用的高斯误差构造是

$$
Z\sim\mathcal N\left(0,\frac{r^2}{2\pi}\right),
\qquad
e=\lfloor Z\rceil,
$$

其中 $\lfloor Z\rceil$ 表示取最近整数。这里 $r$ 沿用第 09 篇的高斯尺度约定，取整前的标准差为

$$
\sigma=\frac{r}{\sqrt{2\pi}}.
$$

常记 $r=\alpha q$，用 $\alpha$ 表示高斯尺度相对于模数的大小。这与 Regev 原始论文的周期化、离散化高斯约定相衔接。见 [Regev《On Lattices, Learning with Errors, Random Linear Codes, and Cryptography》，2009-05-02 作者稿，§2，PDF 第 14–15 页，式 (7)–(8)](https://cims.nyu.edu/~regev/papers/qcrypto.pdf)。

需要保留两个区分：

- 连续高斯取整与第 09 篇的离散高斯 $D_{\mathbb Z,r}$ 通常不是同一个分布。
- 高斯误差没有固定的绝对上界；对误差长度的控制通常是高概率保证。

因此，LWE 的参数需要说明 $n,m,q$ 和完整的误差分布 $\chi$，不能只写“加入少量噪声”。

## 3. 搜索 LWE 与判定 LWE

**搜索 LWE：恢复秘密。**

给定按第一节生成的 $(A,b)$，目标是恢复生成这些样本时使用的 $s$。相应参数可记为

$$
\mathrm{LWE}_{n,m,q,\chi}.
$$

对选定的渐近参数族，搜索 LWE 困难假设要求：任意概率多项式时间算法恢复 $s$ 的成功概率都是可忽略的。概率计入 $A,s,e$ 的抽样和算法自身的随机性。

**判定 LWE：区分两类分布。**

考虑

$$
\mathcal D_{\mathrm{LWE}}
=
\left(A,A^{\mathsf T}s+e\bmod q\right)
$$

与

$$
\mathcal D_{\mathrm U}
=
(A,u),
\qquad
u\leftarrow U(\mathbb Z_q^m).
$$

两类分布中的 $A$ 都均匀随机；第二类中的 $u$ 与 $A$ 独立。

判定任务是识别输入来自哪一类分布。区分器 $D$ 的优势定义为

$$
\boxed{
\operatorname{Adv}_D
=
\left|
\Pr[D(\mathcal D_{\mathrm{LWE}})=1]
-
\Pr[D(\mathcal D_{\mathrm U})=1]
\right|.
}
$$

判定 LWE 困难假设要求所有概率多项式时间区分器的优势都可忽略。这里的要求是**计算上难以区分**，并不要求两类分布在统计上接近。

在素数模数 $q\le\operatorname{poly}(n)$、允许使用多项式数量样本的标准设置下，可以利用判定算法构造搜索算法，即

$$
\text{搜索 LWE}\ \le_{\mathrm{poly}}\ \text{判定 LWE}.
$$

这一归约有明确的模数、样本和成功概率条件，不能理解为任意固定样本数下的无条件等价。见 [Regev《The Learning with Errors Problem》，§3，PDF 第 12–13 页，Lemma 3.1–3.2](https://cims.nyu.edu/~regev/papers/lwesurvey.pdf)。

## 4. 格解释与有界距离解码

沿用第十二篇的模像格

$$
\Lambda_q(A)
=
\left\{
v\in\mathbb Z^m:
v\equiv A^{\mathsf T}t\pmod q
\text{，某个 }t\in\mathbb Z_q^n
\right\}.
$$

取观测向量 $b$ 的整数代表 $\widetilde b$。由 LWE 方程直接得到

$$
v=\widetilde b-e\in\Lambda_q(A),
$$

因此

$$
\boxed{
\operatorname{dist}\bigl(\widetilde b,\Lambda_q(A)\bigr)
\le\|e\|_2.
}
$$

也就是说，观测点位于模像格中某个格点的附近。这一格解释见 [Micciancio，§2，PDF 第 4 页](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/Lec4-Random.pdf)。

若进一步满足

$$
\boxed{
\|e\|_2
<
\frac12\lambda_1\bigl(\Lambda_q(A)\bigr),
}
$$

则 $v$ 是 $\widetilde b$ 的唯一最近格点。因为对任何其他格点 $w\ne v$，有

$$
\|\widetilde b-w\|_2
\ge
\|w-v\|_2-\|e\|_2
\ge
\lambda_1\bigl(\Lambda_q(A)\bigr)-\|e\|_2
>
\|e\|_2.
$$

这给出**有界距离解码**（Bounded Distance Decoding，BDD）的视角：在目标点足够靠近格的承诺下，恢复其唯一最近格点。

恢复 $v$ 后，若 $q$ 为素数且 $A$ 满行秩，再解

$$
A^{\mathsf T}s\equiv v\pmod q
$$

即可唯一恢复秘密。一般 LWE 定义本身并不自动保证上述距离条件；使用 BDD 解释时需要核对参数。

## 5. 与 SIS 的联系

对同一个矩阵 $A$：

- SIS 在模核格 $\Lambda_q^\perp(A)$ 中寻找短的非零向量。
- 搜索 LWE 从模像格 $\Lambda_q(A)$ 附近的观测中恢复秘密。

第十二篇已经给出两类格的缩放对偶关系。还可以直接从方程看出它们之间的联系。

若找到一个 SIS 关系

$$
Ax\equiv0\pmod q,
$$

则对 LWE 样本有

$$
\begin{aligned}
x^{\mathsf T}b
&\equiv x^{\mathsf T}A^{\mathsf T}s+x^{\mathsf T}e\\
&=(Ax)^{\mathsf T}s+x^{\mathsf T}e\\
&\equiv x^{\mathsf T}e
\pmod q.
\end{aligned}
$$

因此，**模核中的关系可以消去秘密项，留下误差的整数线性组合。**

这个组合的取模前大小满足

$$
|x^{\mathsf T}e|
\le
\|x\|_2\|e\|_2.
$$

短关系有助于控制组合后的噪声。但能否据此区分 LWE 样本，还取决于关系长度、误差分布与模数，不能仅凭存在一个 SIS 解就得出结论。

## 6. 困难性来源与后续阅读

Regev 的原始结果在特定高斯误差和参数条件下，建立了从最坏情况近似格问题到随机 LWE 的**量子归约**。

其含义是：若能高效求解相应的 LWE，就能通过量子算法高效解决对应近似因子的最坏情况 GapSVP 和 SIVP。这里的量子性属于归约过程，LWE 样本本身仍由经典运算生成。见 [Regev，2009-05-02 作者稿，PDF 第 2 页，Theorem 1.1](https://cims.nyu.edu/~regev/papers/qcrypto.pdf)。

本篇先建立样本分布与计算任务。后续结合离散高斯和平滑参数学习归约，再以 Regev 公钥加密理解：合法解密如何控制误差，安全性证明如何使用判定 LWE。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)