格理论与后量子密码学：从 NTRU 到 ML-KEM 的数学基础与工程实现

当量子计算机从理论走向工程现实，支撑当今互联网安全的 RSA 与椭圆曲线密码都将在多项式时间内被 Shor 算法击溃。格密码（Lattice-based Cryptography）作为后量子密码标准化进程的核心力量，不仅拥有最坚实的数学困难问题基础，还在安全性、效率与功能性之间取得了独特平衡。本文将深入格理论的数学腹地，从 Minkowski 定理到 LWE 问题，从 NTRU 的历史演变到 NIST 标准化的 ML-KEM 机制，全方位解析这一正在重塑全球安全基础设施的数学工具。

一、为什么我们需要后量子密码？

1994 年，数学家 Peter Shor 证明了一个颠覆性的结论：在量子计算机上，整数分解（IFP）和椭圆曲线离散对数（ECDLP）问题都可以在多项式时间内求解。这意味着一旦足够规模的容错量子计算机问世，当今互联网中广泛部署的 RSA、ECC、Diffie-Hellman 和 DSA 密钥交换与数字签名方案将全部失效。

更严峻的是"先存储后解密"（Harvest Now, Decrypt Later）攻击模型——攻击者可以在今天截获加密通信，等待量子技术成熟后再解密。对于需要长期保密的数据（如政府机密、医疗记录、金融基础设施密钥），威胁已经存在。

美国国家标准与技术研究院（NIST）自 2016 年启动后量子密码标准化进程，经过多轮筛选，于 2024 年正式发布首批三项标准：ML-KEM（FIPS 203）、ML-DSA（FIPS 204）和 SLH-DSA（FIPS 205）。其中 ML-KEM 作为密钥封装机制，是唯一基于格理论（Module-LWE）的标准化方案。

二、格的数学基础

2.1 格的定义与几何直觉

给定 n 个线性无关向量 $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_n \in \mathbb{R}^m$（其中 m ≥ n），由这些向量整数线性组合构成的集合：

$$\mathcal{L} = \left\{ \sum_{i=1}^{n} z_i \mathbf{b}_b \mid z_i \in \mathbb{Z} \right\}$$

称为一个 格（Lattice）。向量组 $\mathbf{B} = [\mathbf{b}_1, \ldots, \mathbf{b}_n]$ 称为格的基（Basis），n 是格的秩（Rank），m 是格的维度（Dimension）。同一个格可以有无穷多组基——好的基（向量短且互相正交）与坏的基（向量长且高度倾斜）之间的区分，正是格密码学的核心利用点。

2.2 基本区域与行列式

格的基本区域（Fundamental Parallelepiped）体积定义为：

$$\det(\mathcal{L}) = \sqrt{\det(\mathbf{B}^T \mathbf{B})}$$

这个值在基变换下保持不变，是格的一个本质几何不变量。对于满秩格（n = m），$\det(\mathcal{L}) = |\det(\mathbf{B})|$。直观地说，行列式的倒数 1/det 控制着格点的"密度"——行列式越小，格点越密集。

2.3 Minkowski 凸体定理

1896 年 Hermann Minkowski 提出的凸体定理是格理论中最优美的结果之一：

设 $\mathcal{L}$ 是 n 秩格，S 是原点左右对称的凸体，若 $\text{vol}(S) > 2^n \det(\mathcal{L})$，则 S 包含非零格点。

这个定理揭示了格点分布与体积之间的深刻联系，直接导出逐次最小值（Successive Minima）的上界：

$$\lambda_1(\mathcal{L}) \leq \sqrt{n} \cdot \det(\mathcal{L})^{1/n}$$

这保证了在任意 n 秩格中，最短向量的长度被行列式严格控制。

2.4 逐次最小值与 Gaussian Heuristic

第 i 个逐次最小值 $\lambda_i(\mathcal{L})$ 定义为包含 i 个线性无关格点的最小球半径。对于随机格，Gaussian Heuristic 给出了一个强有力的统计预测：

$$\text{GH}(n) \approx \sqrt{\frac{n}{2\pi e}} \cdot \det(\mathcal{L})^{1/n}$$

这一预测对密码分析至关重要——它告诉我们"平均"情况下最短向量有多长，从而指导参数选择以抵抗已知攻击。

三、格中的困难问题

格密码的安全性建立在格上几个著名的计算困难问题上。这些问题的特别之处在于：它们在最坏情况（worst-case）下的困难性已被证明，而不仅仅依赖于平均情况的假设。

3.1 最短向量问题（SVP）

问题陈述：给定格的一组基，寻找非零格向量 $\mathbf{v} \in \mathcal{L}$ 使得 $\|\mathbf{v}\| = \lambda_1(\mathcal{L})$。

精确 SVP 在任意维度下都是 NP-hard 问题（Ajtai, 1998）。密码学中通常使用近似版本 $\text{SVP}_\gamma$，其中近似因子 $\gamma = \text{poly}(n)$，此时问题复杂度显著降低但仍被认为指数困难。

经典求解算法包括：

• 枚举法（Enumeration）：确定性搜索，时间 $2^{O(n \log n)}$，空间 $O(n)$
• 筛法（Sieving）：随机化算法，时间 $2^{0.292n + o(n)}$（BDGL），空间 $2^{0.208n}$
• 切片筛法（Triple Sieve）：最新进展，时间 $2^{0.257n}$
• Voronoi Cell：理论最优 $2^{O(n)}$ 时间空间，但实用价值有限

3.2 最近向量问题（CVP）

给定格基和目标向量 $\mathbf{t} \in \mathbb{R}^m$，寻找格点 $\mathbf{v}$ 使得 $\|\mathbf{t} - \mathbf{v}\|$ 最小。CVP 至少和 SVP 一样困难，且可在近似因子 $\gamma = \text{poly}(n)$ 下互相归约。

实际求解中，Babai 最近平面算法（Nearest Plane）和舍入算法（Rounding）是常用启发式方法，但它们的近似因子依赖于基的质量（以正交性缺陷衡量）。

3.3 最短独立向量问题（SIVP）

寻找 n 个长度均不超过 $\gamma \cdot \lambda_n(\mathcal{L})$ 的线性无关格向量。这是安全性证明中最常用的归约目标问题。

3.4 带错误学习问题（LWE）

2005 年，Oded Regev 提出的 LWE 问题将格困难问题与随机噪声融合，成为现代格密码的基石：

秘密向量 $\mathbf{s} \in \mathbb{Z}_q^n$，公开随机矩阵 $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$，误差向量 $\mathbf{e}$ 来自离散高斯分布 $\mathcal{D}_{\alpha q}$，给定 $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \mod q)$，恢复 $\mathbf{s}$。

Regev 证明了最坏情况格困难问题（$\text{SVP}_{O(\sqrt{n}/\alpha)}$）到 LWE 的量子归约。后续的经典归约（Peikert, 2009; Brakerski 等, 2013）使其脱离对量子计算的依赖。

LWE 的困难性依赖于三个参数维度：

• 模数 q：通常取 $q \approx n^2$ 到 $q \approx 2^{13}$
• 维度 n：安全性的主要驱动因素
• 误差比 α：$\alpha q$ 决定误差标准差，通常在 $1/\sqrt{n}$ 量级

3.5 环 LWE（Ring-LWE）与模 LWE（Module-LWE）

纯 LWE 的瓶颈在于密钥和密文尺寸均为 $O(n^2 \log q)$。为提升效率，引入代数结构：

Ring-LWE 在多项式环 $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ 上定义，密钥和密文均为单个多项式（尺寸 $O(n \log q)$），利用数论变换（NTT）实现 $O(n \log n)$ 乘法。代价是安全性归约到理想格上的特殊代数结构，需要额外防范代数攻击。

Module-LWE 是纯 LWE 和 Ring-LWE 之间的中间地带：在 $R_q^k$ 模上运算（k 为模块秩），平衡了效率与保守性。当 k = 1 时退化为 Ring-LWE，当 k = n 时退化为纯 LWE。ML-KEM 正是基于 Module-LWE（k = 2, 3, 4），在保持接近 Ring-LWE 效率的同时，保留了接近纯 LWE 的安全归约紧密度。

四、从 NTRU 到 ML-KEM：格密码的四代演化

4.1 NTRU：开创性的先驱（1996）

由 Hoffstein、Pipher 和 Silverman 于 1996 年设计的 NTRU 是最早被纳入 ISO/IEC 18033 标准的格公钥加密方案。其数学框架基于多项式环 $\mathbb{Z}[x]/(x^N - 1)$（后升级为 $x^n + 1$）。

密钥生成：选择两个小系数短多项式 $f, g \in R$，计算 $f$ 在模 $q$ 下的逆 $f_q$，公钥 $h = f_q \cdot g \mod q$，私钥为 $f$。

加密：随机选取盲化多项式 $r$，密文 $e = r \cdot h + m \mod q$，其中消息 $m$ 编码在系数低位。

解密：计算 $a = f \cdot e \mod q$，则 $a = r \cdot g + f \cdot m \mod q$。由于 $f, g, r$ 都是小多项式，只要参数选择得当，$r \cdot g + f \cdot m$ 的每个系数都在 $(-q/2, q/2)$ 内，无需取模即可还原。再对 $p$ 取模即可提取消息。

NTRU 的优雅之处在于它的正确性本质上依赖一个几何事实：在合适的参数下，短多项式之积仍保持"短"——不会跨越模 $q$ 的边界。

然而 NTRU 历史上遭受过多次结构性攻击（如 Coppersmith-Shamir 对原始 NTRU 的格攻击），其参数选择需要极其谨慎。NIST 第三轮中 NTRU-HRSS 和 NTRU 最终被淘汰，但其设计思想直接影响了 ML-KEM。

4.2 Kyber：NIST 竞赛的胜出者

CRYSTALS-Kyber 由来自欧洲多所研究机构的团队设计，在 NIST 后量子密码标准竞赛中脱颖而出。它基于 Module-LWE 问题，具备以下核心特征：

• 代数结构：在环 $R_q = \mathbb{Z}_{3329}[x]/(x^{256} + 1)$ 上运算
• 模块秩：Kyber-512（k=2）、Kyber-768（k=3）、Kyber-1024（k=4）
• 模数：$q = 3329$（选择满足 $q \equiv 1 \mod 256$，使 NTT 根存在）
• 压缩机制：通过舍入实现密文压缩，减少传输带宽

Kyber 的设计哲学：在合理的保守主义（Module-LWE 而非纯 Ring-LWE）和极致软件效率之间找到甜蜜点。

4.3 ML-KEM：FIPS 203 标准

2024 年 8 月 NIST 将 Kyber 正式标准化为 ML-KEM（Module-Lattice-Based Key Encapsulation Mechanism），三个安全等级对应 NIST 安全等级 I、III、V：

参数集	模块秩 k	维度 n	η₁	η₂	d_u	d_v	公钥大小	密文大小
ML-KEM-512	2	256	3	2	10	4	800 B	768 B
ML-KEM-768	3	256	2	2	10	4	1184 B	1088 B
ML-KEM-1024	4	256	2	2	11	5	1568 B	1568 B

ML-KEM 的核心流程：

密钥生成（KeyGen）：

1. 随机种子 $d \in \{0,1\}^{32}$
2. 扩展生成矩阵 $\mathbf{A} \in R_q^{k \times k}$
3. 采样秘密向量 $\mathbf{s}, \mathbf{e}$ 来自中心二项分布 $\beta_\eta$
4. 公钥 $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$
5. 输出 $(pk = (\mathbf{t}, d), sk = \mathbf{s})$

封装（Encapsulate）：

1. 随机消息 $m \in \{0,1\}^{32}$
2. 使用 FO（Fujisaki-Okamoto）变换的隐式拒绝模式：$(K, r) = G(H(pk) \| m)$
3. 采样 $\mathbf{r}, \mathbf{e}_1, \mathbf{e}_2$ 来自 $\beta_\eta$
4. 计算 $\mathbf{u} = \mathbf{A}^T \mathbf{r} + \mathbf{e}_1$，$v = \mathbf{t}^T \mathbf{r} + \mathbf{e}_2 + \text{Decode}(m)$
5. 压缩后输出密文 $c = (\text{Compress}(\mathbf{u}), \text{Compress}(v))$ 和共享密钥 $K$

解封装（Decapsulate）：

1. 解密 $m' = \text{Decompress}(v) - \mathbf{s}^T \cdot \text{Decompress}(\mathbf{u})$
2. 重新加密验证：计算 $(c', K')$ 与接收到的密文比较
3. 若匹配，输出 $K = K'$；否则输出 $K = H(sk \| c)$（隐式拒绝，避免 CCA 攻击）

五、数论变换（NTT）：格密码的计算引擎

5.1 从 DFT 到 NTT

在 $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ 中执行多项式乘法，朴素算法需要 $O(n^2)$ 次模乘。FFT 在复数域上将卷积转为逐点乘，但引入浮点误差。NTT（数论变换）是有限域/环上的精确模拟：

若 $q$ 是素数且 $q \equiv 1 \mod 2n$，则存在 2n 次本原单位根 $\omega \in \mathbb{Z}_q$。NTT 将多项式在 n 个求值点 $\{\omega^{2i+1}\}_{i=0}^{n-1}$ 上求值（"蝴蝶"结构等价于 FFT 的 Cooley-Tukey 分解）。正向 NTT 和逆向 NTT（INTT）将系数表示转为点值表示，实现 $O(n \log n)$ 乘法：

$$c(x) = \text{INTT}(\text{NTT}(a) \circ \text{NTT}(b)) \mod (x^n + 1, q)$$

其中 $\circ$ 为逐点模乘。

5.2 Kyber 的 NTT 细节

Kyber 选择 $q = 3329$ 满足 $3329 \equiv 1 \mod 512$（更精确地，3329 = 256 × 13 + 1），因此存在 512 次本原单位根。但实际运算在 $x^{256}+1$ 上，需要 256 次本原单位根，而 13 阶单位根的平方 $\zeta = 13^2 \mod 3329 = 169$ 恰好是 256 次本原根。

NTT 采用"混合基"分解：256 = 2^8，执行 8 层蝴蝶操作。每层利用 Gentleman-Sande 变体（逆序输入、正序输出），配合 Barrett 约简实现高效的模运算：

// Barrett reduction for q=3329
uint16_t barrett_reduce(uint32_t a) {
    const uint32_t v = ((1U << 26) + q/2) / q; // v ≈ 2^26/q
    uint32_t t = ((uint64_t)a * v) >> 26;
    return a - t * q;
}

5.3 安全与优化的权衡：无填充乘法

为防御侧信道攻击，现代格密码实现通常采用"无分支编程"——避免条件跳转、确保内存访问模式独立于秘密数据。NTT 的蝴蝶结构天然适合向量化（AVX2/NEON），在 x86-64 上单次 NTT 仅需约 1000 个时钟周期。

ARM Cortex-M4 上的 pqm4 项目展示了：Kyber-768 的密钥生成仅需约 120 万次时钟周期，封装约 150 万次，解封装约 170 万次——对于资源受限的嵌入式设备也完全可行。

六、安全分析：攻击向量与防御策略

6.1 格约简攻击

针对格密码最经典的攻击手段是 LLL 和 BKZ 类格约简算法。BKZ（Block Korkine-Zolotarev）以块大小 β 为参数：

• BKZ-β 每轮在 β 维格上执行枚举或筛法求解 SVP，迭代改善基质量
• 时间复杂度约 $2^{0.292\beta}$（筛法）到 $2^{O(\beta \log\beta)}$（枚举）
• 约简后与最短向量的近似因子为 $\gamma_\beta^{n/(2(\beta-1))}$

安全分析通过"格估计器"（Lattice Estimator，如 Albrecht 等人的 alwe 工具）计算攻破给定参数集所需的最小 β 及对应时间，保证攻击代价超过 $2^\lambda$ 操作（λ = 目标安全位数）。

6.2 代数攻击

Module-LWE 引入的代数结构可能被利用：数域筛法（NFS）在特定数域上求解最短向量的速度优于通用格约简。对于 ML-KEM 所用的分圆域 $\mathbb{Q}(\zeta_{512})$，NFS 的渐近复杂度由pecial-q技术决定。安全评估需确保代数攻击不优于通用策略。

6.3 侧信道与实现攻击

格密码不是天生免疫侧信道的。实际攻击面包括：

• 时序攻击：条件分支或数据相关的数组访问可能泄露密钥比特
• 缓存攻击：NTT 蝴蝶的内存访问模式可能反映密钥信息
• 故障注入：激光或电压毛刺可导致解密错误并泄露密钥（如 Bellcore 攻击对 RSA 的变体）
• 能量分析：SPA/DPA 分析乘法器的能量消耗模式

对策措施包括常数时间实现、掩码（Shamir 秘密共享拆分秘密）、随机化 NTT 访问模式等。

七、TLS 后量子迁移工程实践

7.1 混合密钥交换

在过渡期间，业界采用"混合"模式：同时执行经典 ECDH 和 ML-KEM，将两者输出拼接后输入 KDF。这样既能够抵御量子攻击（只要任一组件安全），又维持了对经典攻击的防护。

Google 的 CECPQ2（X25519 + Kyber-768）已在 Chrome 中部署，Cloudflare 和 Facebook 的实测数据显示混合方案增加的延迟小于 1ms。X25519Kyber768 已被标准化为 TLS 密码套件（draft-ietf-tls-hybrid-design）。

7.2 握手消息扩展

TLS 1.3 握手需扩展以携带后量子公钥和密文。以 ML-KEM-768 为例：公钥增加 1184 字节，密文增加 1088 字节，ClientHello 总大小增加约 2.3 KB。这在现代互联网中通常可接受，但对某些嵌入式场景需要评估。

一种优化是使用 KEMTLS（TLS 1.3 的后量子变体），利用 KEM 替代数字签名进行认证，可减少握手往返——在 RTT 敏感场景（如卫星通信）尤为有价值。

7.3 证书链与信任模型

后量子证书迁移涉及 CA 基础设施的全面升级。IETF 的 LAMPS 工作组正在制定 X.509 后量子证书标准，定义 ML-DSA/ML-KEM 的 OID 和编码规则。

通常采用"复合证书"方案：一个 X.509 v3 证书包含多个公钥（经典 + 后量子），验证时选择对应签名方案。国际电信联盟（ITU）的 X.509 第 9 版已支持多算法证书结构。

八、格密码的前沿方向

8.1 全同态加密（FHE）

基于 LWE/RLWE 的 FHE（Brakerski-Gentry-Vaikuntanathan, 2011 至今）使在加密数据上直接计算成为可能。CKKS 方案支持近似实数运算，ML-KEM 和 CKKS 共享底层积木（NTT、误差管理），FHE 开销从最初的 $10^{10}$ 倍已降低到 $10^4$–$10^5$ 倍，在隐私保护机器学习推理等场景开始走向实用。

8.2 零知识证明

Lattice-based ZKP（如 LatticeFold、LaBRADOR）利用格承诺（Ajtai 承诺）构造后量子安全的零知识证明。相比基于椭圆曲线的 Groth16/PLONK，格 ZKP 的证明尺寸更大，但不受量子计算威胁，且天然支持同态特性。

8.3 硬件加速

各大半导体厂商已开始布局后量子密码硬件：ARM 的 ARMv8.4 加密扩展新增多项式乘法指令；RISC-V 后量子密码扩展（PQC-EXT）定义 NTT 专用指令；Intel 和 AMD 的 AVX-512 可通过 IFMA 指令加速模乘。专用 ASIC 实现中，Kyber-768 的封装吞吐量可达每秒百万次（@500MHz）。

8.4 更高安全性的参数集

NIST 2024 年启动了第四轮征集，面向"附加算法"——特别是针对 ML-KEM-1024 以上安全等级（NIST V+）、抗多目标攻击和故障注入的方案。Classic McEliece（基于纠错码）虽然参数巨大（公钥 > 1MB），但已纳入备选，为高保障场景提供算法多样性。

九、总结

格密码的崛起并非偶然。它在三个维度上取得了独特的优势：安全性根基深厚（最坏情况到平均情况的紧归约）、效率优异（接近经典 RSA/ECC）、功能丰富（天然支持同态加密和零知识证明）。从 1996 年 NTRU 的开创性探索，到 2024 年 ML-KEM 正式成为 NIST 标准，格理论经历了从纯数学到全球安全基础设施核心组件的蜕变。

对于安全工程师和系统架构师而言，今天是开始规划和向后量子密码迁移的最晚时间窗口。TLS 混合模式、X.509 复合证书、硬件 Roots of Trust 的升级——每一个环节都需要工程规划与供应链协调。量子计算的威胁或许还需 10–15 年才能充分实现，但密码迁移的周期更长，等待的代价可能是整个数字信任体系的被动瓦解。

格的数学之美在于它连接了几何、代数和信息论，将高维空间中的几何难题转化为保护数字世界的工具。后量子密码学不是一项静态的标准，而是数学、密码学与工程持续碰撞的前沿战场。