整理日期：2026-10-16。
前置笔记：09 高斯函数与离散高斯分布、12 q 元格与模线性方程、13 SIS 问题与短整数关系。
本文采用整数误差形式，向量按列排列，长度使用欧氏范数。
1. 从带噪方程到 LWE 样本#
带误差学习问题（Learning with Errors，LWE）研究从带有随机误差的模线性方程中恢复秘密，或识别这些方程的分布。
设 \(q\ge2\)，秘密为
误差分布 \(\chi\) 定义在 \(\mathbb Z\) 上，通常集中在 \(0\) 附近。
固定秘密 \(s\) 后，一个 LWE 样本按以下方式生成：
公开的是 \((a,b)\)，秘密 \(s\) 和误差 \(e\) 不公开。部分文献直接将误差分布定义在 \(\mathbb Z_q\) 上，对应这里的整数误差取模后的分布。样本定义见 Regev《The Learning with Errors Problem》，CCC 2010，§1，PDF 第 2 页。
将 \(m\) 个样本合并，记
便得到
这里 \(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\) 满行秩，那么
可以通过有限域上的线性消元唯一求解。
加入未知误差后，对方程作线性组合时，误差也随之组合。模 \(q\) 上的可逆变换一般不保持整数误差的短性，因此直接消元不再自动恢复秘密。
“小误差”描述的是取模前的整数大小。例如，模 \(q\) 的剩余类 \(q-1\) 可以来自误差 \(-1\)。
一个常用的高斯误差构造是
其中 \(\lfloor Z\rceil\) 表示取最近整数。这里 \(r\) 沿用第 09 篇的高斯尺度约定，取整前的标准差为
常记 \(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\)。相应参数可记为
对选定的渐近参数族，搜索 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)\)、允许使用多项式数量样本的标准设置下，可以利用判定算法构造搜索算法，即
这一归约有明确的模数、样本和成功概率条件，不能理解为任意固定样本数下的无条件等价。见 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 方程直接得到
因此
也就是说，观测点位于模像格中某个格点的附近。这一格解释见 Micciancio，§2，PDF 第 4 页。
若进一步满足
则 \(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\) 满行秩，再解
即可唯一恢复秘密。一般 LWE 定义本身并不自动保证上述距离条件；使用 BDD 解释时需要核对参数。
5. 与 SIS 的联系#
对同一个矩阵 \(A\)：
- SIS 在模核格 \(\Lambda_q^\perp(A)\) 中寻找短的非零向量。
- 搜索 LWE 从模像格 \(\Lambda_q(A)\) 附近的观测中恢复秘密。
第十二篇已经给出两类格的缩放对偶关系。还可以直接从方程看出它们之间的联系。
若找到一个 SIS 关系
则对 LWE 样本有
因此，模核中的关系可以消去秘密项，留下误差的整数线性组合。
这个组合的取模前大小满足
短关系有助于控制组合后的噪声。但能否据此区分 LWE 样本，还取决于关系长度、误差分布与模数，不能仅凭存在一个 SIS 解就得出结论。
6. 困难性来源与后续阅读#
Regev 的原始结果在特定高斯误差和参数条件下，建立了从最坏情况近似格问题到随机 LWE 的量子归约。
其含义是：若能高效求解相应的 LWE，就能通过量子算法高效解决对应近似因子的最坏情况 GapSVP 和 SIVP。这里的量子性属于归约过程，LWE 样本本身仍由经典运算生成。见 Regev，2009-05-02 作者稿，PDF 第 2 页，Theorem 1.1。
本篇先建立样本分布与计算任务。后续结合离散高斯和平滑参数学习归约，再以 Regev 公钥加密理解：合法解密如何控制误差，安全性证明如何使用判定 LWE。