4. 同态加密的数学基础：格理论、LWE问题
老规矩，聊同态加密的数学基础，咱们得先从格（Lattice）讲起。为什么？因为几乎所有现代实用化的 FHE 方案，底子都是格上的困难问题。我当年刚接触时也觉得格很抽象，不就是一些点的集合嘛。后来踩了坑才发现，参数选错一点点，安全性和性能就全崩了。
4.1 格到底长什么样？
格，说白了就是 n 维空间里一组离散的、有周期性的点的集合。换个说法，它是由若干个线性无关的基向量张成的所有整系数线性组合。
数学上这么写：L = { a₁·b₁ + a₂·b₂ + … + aₙ·bₙ | aᵢ ∈ ℤ }
其中 b₁, …, bₙ 是基向量。注意系数必须是整数——这跟线性空间不一样，线性空间允许实数系数。
举个例子，二维平面上取基向量 (1,0) 和 (0,1)，所有整数坐标点 (x,y) 就构成一个方形格。取 (2,0) 和 (1,1) 也能张出一个平行四边形格。
我在项目中遇到过一种情况：用同一个格做不同方案的参数，结果一个要跑 10 秒，另一个要跑 100 秒。问题出在哪？格基的“质量”不一样。好的基几乎正交，用起来快；坏的基又长又歪，运算代价高。
关键认识：格的困难性恰恰来自于“基的选择”——给定一个“坏基”很难还原出“好基”。这就是格密码的立足之本。
4.2 格上的经典困难问题
同态加密之所以安全，是因为攻击者要解下面这两个问题中的一个。
- SVP（最短向量问题）：在格中找一个长度最短的非零向量。你想想看，给定一堆乱糟糟的基，要找到最短的那个向量，就像在一堆钢丝里抽出最短的那根，还戴着手套。
- CVP（最近向量问题）：给一个不在格上的目标点，找到离它最近的格点。这个更贴近 LWE 的构造。
实际密码学里，我们一般不直接攻 SVP，而是用它的变体——GapSVP（判定型最短向量）或者 BDD（有界距离解码）。这些问题的难易程度直接决定了你的密钥该设多大。
| 问题 | 全称 | 密码学角色 | 难度现状 |
|---|---|---|---|
| SVP | 最短向量问题 | 安全性根基 | 指数级难度（量子算法下仍难） |
| CVP | 最近向量问题 | LWE 的冗余解释 | 比 SVP 稍难 |
| LWE | 带误差学习 | 直接用于加密 | 由 SVP 归约保证 |
| RLWE | 环带误差学习 | 性能优化核心 | 归约到理想格 SVP |
我个人习惯，在工程中选择参数时先查一下当前主流的 LWE 挑战赛榜单，看看同样安全强度下别人用了多大的模数和向量维度。这比纯理论推导靠谱得多。
4.3 LWE 问题：从格到加密的桥梁
LWE（Learning With Errors）是 Oded Regev 在 2005 年提出来的，当年直接拿了 Gödel Prize。它的定义很简单，但威力极大。
- 你有一组随机向量
a₁,…,aₘ和对应的标量bᵢ = ⟨aᵢ, s⟩ + eᵢ，其中s是秘密向量，eᵢ是小噪声。 - 攻击者能拿到所有
(aᵢ, bᵢ)，但要恢复s却极难。为什么？因为eᵢ打破了线性关系。 - 决策型 LWE 问的是：给你一堆
(a,b)，你能不能区分它们是来自上面的过程还是纯随机数？
说白了，LWE 就是一个“加了一点噪声的线性方程系统”。在正确解附近有无数个候选，因为噪声的存在让你无法确定哪一个是真实的 s。
// 一个极简的 LWE 加密示例（仅示意逻辑）
// 参数：n=4, q=17, 噪声 e~[-1,1]
秘密 s = [2, 4, 1, 3]
随机向量 a = [3, 7, 2, 5]
噪声 e = 1
b = (3*2 + 7*4 + 2*1 + 5*3) mod 17 + 1 = (6+28+2+15) mod 17 +1 = 51 mod 17 +1 = 0+1 = 1
// 公开 (a,b) = ([3,7,2,5], 1)
// 攻击者要解 s，但无法知道 e 是 1嗯，这里要注意：上面的例子为了展示用小参数，实际中 n 至少 256, q 几千比特，噪声分布是高斯型。我当年试过自己实现 LWE 加密，拿 n=64 跑，结果 10 秒破解。从此再也不敢小瞧参数选择。
我曾经踩过的一个坑：LWE 的噪声分布用均匀分布替代高斯分布，觉得差不多。结果安全强度直接掉了两个等级。Regev 的归约证明依赖于离散高斯分布，换分布会破坏安全性归约。千万别自作聪明换噪声。
4.4 从 LWE 到环 LWE（RLWE）
同态加密要实用，光靠 LWE 不够——计算开销太高。RLWE 把向量塞进多项式环里，一次操作能处理整个向量，性能提升好几个数量级。
- 普通 LWE 的向量是
ℤ_qⁿ，加密一个比特对应n+1个ℤ_q元素。 - RLWE 的向量是
ℤ_q[X]/(Xⁿ+1)里的多项式，加密一个多项式对应n个ℤ_q元素。 - 但 RLWE 的安全性归约依赖于理想格上的 SVP，目前没有已知的量子攻击能显著加速。
现在的 BFV、BGV、CKKS 方案全用的是 RLWE。你想想看，没有 RLWE，同态加密的 bootstrapping 可能要跑几小时，现在只需要几分钟。
4.5 格与 LWE 知识体系一览
下面这张图是我梳理的格 → LWE → 同态加密的脉络。每个节点对应一个核心概念，箭头表示归约或构造关系。
4.6 格参数选择与工程避坑
最后聊点实在的。在工程中使用格基密码，参数选择是第一道坎。我建议你记住这三点：
- 安全强度对齐 NIST 标准：一般选 λ=128 或 256。用 LWE 参数估算工具（如
lwe-estimator）跑一遍，别凭感觉设。 - 噪声预算：同态加密里噪声会随乘法增长。初始噪声大约
B ≈ n·σ，乘法后变成B²。如果方案层深是 L，那初始噪声得留足B^(2^L)的衰减空间。 - 模数 Q 的选择：Q 要够大，保证解密正确；但太大又拖慢速度。通常 Q 选 2^60 左右，配合残数系统 RNS 加速。
我看过不少开源项目直接拿 demo 参数（n=2048, q=2^60）上生产，结果 CPU 跑 bootstrapping 要 3 秒。后来改用 n=4096, q=2^80 后降到了 0.5 秒——虽然安全强度没变，但噪声管理更优。参数调优是门手艺活。
嗯，这一章的内容就到这。格和 LWE 的数学基础是理解同态加密的必经之路，以后讲到 bootstrapping 和密钥切换时，你会反复遇到它们。