3. 格密码数学基础

格密码之所以能成为后量子迁移的主力方案，核心在于它把安全性建立在几何与代数结构上的一类困难问题上。理解格密码，第一步不是记住某个算法，而是先建立“格”这个几何对象，再理解它上面哪些问题难、难到什么程度，以及如何把这些问题变成可用的密码构造。

格的定义：离散的周期点阵

设 b₁, b₂, …, bₙ 是实数空间 ℝⁿ 中一组线性无关的向量，则由它们的所有整数线性组合构成的集合

L = { Σᵢ zᵢ·bᵢ | zᵢ ∈ ℤ }

称为一个 格，b₁…bₙ 称为格的一组基，n 称为格的维数。直观上，格是空间中规则排列的离散点集：它不像连续空间那样稠密，而是像晶体点阵一样有周期结构。同一个格可以有无穷多组不同的基，其中有些基向量很长、彼此接近平行，有些基向量很短、接近正交。这种“同一格、不同基”的性质，正是格密码安全性的重要来源。

格的基本几何量包括：最短向量长度 λ₁(L)，即格中非零最短向量的长度；行列式 det(L)，等于基向量张成的平行多面体体积，反映格点的平均密度。维数越高、行列式越小，格点越密，问题通常越难。

四个核心困难问题：SVP、CVP、SIS、LWE

格上最基础的两个困难问题是 SVP 和 CVP。

• SVP（最短向量问题）：给定格的一组基，找出格中长度最短的非零向量。在一般格上，精确 SVP 是 NP 困难的；即使求近似解（GapSVP），在高维下也被认为没有多项式时间算法。
• CVP（最近向量问题）：给定格的一组基和一个目标点 t，找出格中距离 t 最近的格点。CVP 可以看作 SVP 的“非齐次”版本，同样在高维下困难。

密码构造不能直接使用 SVP/CVP，因为它们描述的是“找最短/最近向量”的搜索问题，不便直接嵌入加解密流程。于是有了两个更适合密码学的平均情形问题：SIS 和 LWE。

• SIS（短整数解问题）：给定随机矩阵 A ∈ ℤ_q^{n×m}，寻找非零短向量 x ∈ ℤ^m，使得 A·x ≡ 0 (mod q)，且 ‖x‖ ≤ β。SIS 是“找短向量落在矩阵核中”的问题，常用于构造哈希函数和签名。
• LWE（带误差学习问题）：给定 m 组样本 (aᵢ, bᵢ)，其中 aᵢ ∈ ℤ_q^n 随机，bᵢ = ⟨aᵢ, s⟩ + eᵢ mod q，s 是秘密向量，eᵢ 是小误差。判定版本要求区分这些样本与完全均匀随机的样本；搜索版本要求恢复 s。LWE 的困难性可归约到一般格上的 GapSVP 等最坏情形问题，这是它成为主流方案的关键原因。

模格与理想格：让格“长”在代数结构上

普通格定义在实数空间上，而密码学需要有限域上的运算。把格的定义搬到模 q 的整数环上，就得到模格：格点坐标取自 ℤ_q，向量加法与数乘都在模 q 意义下进行。SIS 和 LWE 本质上都是模格上的问题。

如果进一步要求格在多项式环 R_q = ℤ_q[x]/(xⁿ+1) 上具有理想结构，即格对环中元素的乘法封闭，就得到理想格。理想格的好处是：一个格可以由单个多项式生成，而不是由 n 个独立基向量描述，存储和运算量大幅下降。Ring-LWE 正是建立在理想格上的 LWE 变体。

高斯分布与离散高斯采样

LWE 中的误差 e 不能随便取，它必须服从一个“足够窄”的分布，才能保证解密正确，同时又不至于让攻击者轻易恢复秘密。最常用的分布是离散高斯分布：在整数点上取值的离散概率分布，概率随离中心距离指数衰减，标准差记为 σ。

采样时通常使用离散高斯采样器，常见实现方式包括：拒绝采样（从连续高斯采样后取整，按概率接受）、累积分布表法（预计算 CDF 后二分查找）、以及基于随机游走的 CDT 采样。工程中还要注意：采样必须做到常数时间或抗侧信道，否则采样时间差异可能泄露秘密信息。参数选择上，σ 太小会导致解密失败率上升，σ 太大会削弱安全性，通常取 σ ≈ 3.2 或与 q、n 匹配的经验值。

从 LWE 到 Ring-LWE / Module-LWE 的演进

原始 LWE 的密钥和密文都是 n 维向量或 n×m 矩阵，尺寸随安全参数平方增长，实际部署代价高。Ring-LWE 把向量替换为多项式环中的元素，一次多项式乘法就等价于 n 维矩阵-向量乘，密钥和密文从 O(n²) 降到 O(n)，同时可用 NTT（数论变换）把多项式乘法加速到 O(n log n)。

但 Ring-LWE 的理想格结构过于特殊，安全性假设较强，参数选择一旦出错可能引入额外弱点。Module-LWE 折中两者：把 k 个多项式组成模 R_q^k 上的向量，既保留多项式环的高效运算，又通过模块秩 k 提供更灵活的安全裕度。Kyber（ML-KEM）和 Dilithium（ML-DSA）都采用 Module-LWE / Module-SIS 框架，这也是 NIST 后量子标准的主流选择。

安全性归约的直观理解

格密码的安全性论证遵循一条核心逻辑链：如果存在算法能破解 LWE，那么就能用它构造算法求解最坏情形下的 GapSVP/SIVP。这就是“最坏情形到平均情形”的归约。它的意义在于：密码系统的安全性不依赖于某个随机实例恰好很难，而是只要最坏情形格问题难，平均情形下的 LWE 就难。这种归约强度是格密码相对于许多传统方案的重要优势，也是它在后量子迁移中被广泛信任的理论基础。