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

整理日期：2026-10-16。
前置笔记：09 高斯函数与离散高斯分布、12 q 元格与模线性方程、13 SIS 问题与短整数关系。

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

#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 页。

将 $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 及其后的分布说明。

#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)。

需要保留两个区分：

• 连续高斯取整与第 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。

#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 页。

若进一步满足

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

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

#引用此笔记

• 00 概览与阅读路线