2.2 草稿纸上的 LWE：q 等于 17 完整推演
2.2 草稿纸上的 LWE：q 等于 17 完整推演
带误差学习问题（LWE, Learning With Errors）：给定形如 b = \langle a, s \rangle + e \bmod q 的大量样本，其中 e 是极小的随机误差，要求恢复秘密 s（搜索版）或判断样本是否真带误差（判定版）。本节用模数 17 的四样本玩具实例，把加密与解密逐行验算一遍，让"误差即安全"从口号变成你亲手算出的结论。
上一节的 SVP 和 CVP 还是纯几何题；LWE 给它们换上代数外衣——这是整个现代格密码最重要的一次翻译，出自 Regev 在 2005 年的工作。翻译完成后，加密方案变成了几行矩阵运算，本节你将顺着 2.1 的几何直觉，把这几行运算在草稿纸上全部走通，并直达 2.3 节 SIS 的对偶世界。
从方程组到密码：一步之遥
先看没有误差的世界。秘密 s=(3,4)，别人拿到若干方程：
两个方程两个未知数，中学生消元三行解出 (3,4)——线性方程组毫无密码学价值。LWE 的全部魔法就一个动作：发布方程时不给 26，给 26 加上一个随机小误差，比如加 1，发布 27。误差哪怕只有正负一，高斯消元的连锁消去也会被污染：你消掉一个变量，误差同时被放大混入另一个变量，消到最后得到的是一个被噪声糊满的方程。
LWE 的正式设定：误差从一个小范围分布 \chi 抽取（玩具用 \{-1,0,1\}，实战用居中二项分布或离散高斯），攻击者拿到 m 个样本 (a_i, b_i)，其中 b_i = \langle a_i, s \rangle + e_i \bmod q。搜索版要求恢复 s；判定版更狠——只要求分辨这些样本和均匀随机的 (a,b) 有何不同。别小看判定版："分不出"恰好是加密方案需要的性质（密文应当像随机数），两者在标准参数下可以互相归约。
完整推演：一个四样本玩具实例
取 n=2，q=17，秘密 s = (3,4)，误差逐个抽得 e = (1, -1, 0, 2)，随机矩阵（每行一个 a_i）：
逐行计算 b = A s + e \bmod 17，每一步都值得你亲自核一遍：
- 第一行：2 \times 3 + 5 \times 4 = 26，加误差 1 得 27，模 17 得 \mathbf{10}；
- 第二行：3 \times 3 + 4 \times 4 = 25，加误差 -1 得 24，模 17 得 \mathbf{7}；
- 第三行：1 \times 3 + 6 \times 4 = 27，误差 0，模 17 得 \mathbf{10}；
- 第四行：7 \times 3 + 2 \times 4 = 29，加误差 2 得 31，模 17 得 \mathbf{14}。
攻击者看到的是四个点对：(2,5;10)、(3,4;7)、(1,6;10)、(7,2;14)。几何解释见下图：每个样本在平面上压出一条宽两个单位的"噪声带"，四条带子交叉的位置就锁住了秘密——但只要带子比格点间距窄、条数够多，交叠处极小，搜索就成了大海捞针；而要判断"带子是否真的交于一点"，在 q、n 取实战值时被证明与最坏情况格难题一样难（第 3 章展开）。
图：LWE 样本即噪声带，秘密藏在带子交叠处
用这副公钥加密一个比特
Regev 方案把样本变成公钥。加密比特 m：随机挑一个样本子集 S，把子集里的样本逐分量求和，再在第二分量上加 m \cdot \lfloor q/2 \rfloor。取 \lfloor 17/2 \rfloor = 8。
加密 1，挑子集 S = \{1, 3\}（第一、三行）：
解密：计算 v = c_b - \langle c_a, s \rangle = 11 - (3 \times 3 + 11 \times 4) = 11 - 53 = -42 \equiv \mathbf{9} \pmod{17}。判断规则：v 落在 \{q/4, \ldots, 3q/4\}（即 4.25 到 12.75）判 1，否则判 0。9 在区间内，输出 \mathbf{1}，正确。核对原理：求和把误差也加了起来——子集误差 1 + 0 = 1，远小于四分之一模数，所以 v = 8m + (\text{小噪声})，m=1 时 9 与 8 只差 1。
加密 0 再来一遍，子集 S = \{2, 4\}：c_a = (3+7, 4+2) = (10, 6)，c_b = 7 + 14 + 0 = 21 \equiv 4 \pmod{17}。解密：v = 4 - (10 \times 3 + 6 \times 4) = -50 \equiv \mathbf{1} \pmod{17}。1 远离 8，判 \mathbf{0}，正确。两次解密你都看到同一个规律：只要累计误差不超过 q/4 \approx 4.25，比特就淹不死。这一句就是第 4 章 Kyber 解密失败率计算的种子。
参数三要素的账本
纸面玩具体验过后，把参数怎么取讲成三笔账。模数 q：必须远大于误差宽度（给噪声留缓冲），又不能太大（密文尺寸按 \log q 涨）；实战取值 3329 到 2^32 量级不等，玩具取 17 是为了手算。维数 n：安全性的主旋钮，攻击成本随 n 指数上涨；Kyber 用的是它的多项式环变体，n 实际为 512、768、1024 三档。误差分布 χ：实战用宽度很小的居中二项分布（参数 \eta，逐系数独立取值），第 7 章参数表里你会见到 \eta = 2 或 3。三者的相互制约构成第 3 章"安全强度估算"的全部内容——这里先记住方向：n 买安全，q 与误差宽度决定密文能塞多少信息。
用代码把本节全部运算复现，二十行以内：
import numpy as np q, s = 17, np.array([3, 4]) A = np.array([[2, 5], [3, 4], [1, 6], [7, 2]]) e = np.array([1, -1, 0, 2]) b = (A @ s + e) % q print("公钥样本 b:", b) # [10 7 10 14] def enc(bit, S): ca = A[list(S)].sum(axis=0) % q cb = (b[list(S)].sum() + bit * (q // 2)) % q return ca, cb def dec(ca, cb): v = (cb - ca @ s) % q # 落在 [0, q) 上 v = v if v <= q // 2 else v - q # 居中到 (-q/2, q/2] return int(abs(v) > q / 4) ca, cb = enc(1, [0, 2]); print("加密 1 解出:", dec(ca, cb)) # 1 ca, cb = enc(0, [1, 3]); print("加密 0 解出:", dec(ca, cb)) # 0
要点速记：LWE 等于"线性方程组加小误差"，误差让消元法失效；样本几何上是被噪声加宽的超平面；解密就是在 q/4 的窗口里读比特；n、q、误差分布三者的制约关系决定安全与效率。
下一节反着走一遍：不再"藏一个 s"，而是"承诺一个短向量"——SIS 与抗碰撞哈希，LWE 的对偶面孔。