【密码学百科】格基后量子方案：ML-KEM（Kyber）与 ML-DSA（Dilithium）深度解析

2024 年 8 月 13 日，美国国家标准与技术研究院（NIST）正式发布了三项后量子密码学联邦信息处理标准：FIPS 203（ML-KEM）、FIPS 204（ML-DSA）和 FIPS 205（SLH-DSA）。这一里程碑事件标志着长达八年的后量子密码标准化竞赛的主体阶段落幕，也宣告格基密码（Lattice-based Cryptography）正式成为后量子时代公钥密码学的基石。在这三项标准中，前两项——密钥封装机制 ML-KEM（Module-Lattice-based Key-Encapsulation Mechanism，原 CRYSTALS-Kyber）与数字签名算法 ML-DSA（Module-Lattice-based Digital Signature Algorithm，原 CRYSTALS-Dilithium）——均构建在模格（Module Lattice）上的困难问题之上，共享相同的代数框架和底层运算原语。

本文将从格困难问题的数学基础出发，逐步深入 ML-KEM 和 ML-DSA 的算法内部结构，剖析数论变换（Number Theoretic Transform, NTT）等核心运算的实现细节，讨论 Fujisaki-Okamoto 变换和 Fiat-Shamir with Aborts 等关键密码学构造的设计逻辑，分析安全性证明的核心假设，并探讨工程实现中的优化策略与当前的部署进展。

一、从 LWE 到 Module-LWE

先看一张图，把这一节的关键关系串起来。

graph LR
    SVP[格难题]
    LWE[LWE]
    MLWE[MLWE]
    NTT[NTT]
    KEM[ML-KEM]
    DSA[ML-DSA]
    FO[Fujisaki-Okamoto]
    FS[Fiat-Shamir]
    SVP --> LWE --> MLWE
    MLWE --> KEM
    MLWE --> DSA
    NTT --> KEM
    NTT --> DSA
    FO --> KEM
    FS --> DSA

格与格问题

格（Lattice）是 n 维欧几里得空间中由一组线性无关的基向量通过整系数线性组合生成的离散点集。形式化地说，给定基矩阵 B = [b_1, b_2, …, b_n]，格 L(B) = { Bx : x ∈ Z^n }。格上的计算困难问题是后量子密码学最重要的安全根基之一。其中，最短向量问题（Shortest Vector Problem, SVP）要求在给定格中找到一个非零的最短格向量；最近向量问题（Closest Vector Problem, CVP）则要求找到格中离给定目标点最近的格向量。这两个问题在最坏情况下都是 NP 困难的，而更重要的是，目前尚无已知的量子算法能对它们提供超多项式加速——Shor 算法的离散对数/因子分解技巧在格问题的结构上找不到着力点。

LWE 问题

带误差学习问题（Learning with Errors, LWE）由 Oded Regev 于 2005 年提出，它将格困难问题转化为一个更适合构建密码方案的形式。LWE 问题的核心是：给定一个随机矩阵 A ∈ Z_q^{m×n}、一个秘密向量 s ∈ Z_q^n 和一个小误差向量 e ∈ Z_q^m（各分量按离散高斯分布或中心二项分布采样），求解者得到 (A, b = As + e mod q)，需要恢复 s 或区分 b 与均匀随机向量。Regev 证明了 LWE 问题在平均情况下的困难性可以归约到格上最坏情况的近似 SVP 问题——这一最坏情况到平均情况的归约是格基密码学最深刻的理论成果之一。

Regev 归约的核心逻辑

Regev 2005 年结果的深刻之处值得用更易理解的方式阐述。用一句话概括其含义：如果你能破解随机生成的 LWE 问题，你就能破解任何给定格上最困难的格问题——而我们坚信，即使量子计算机也做不到后者。 这就是所谓”最坏情况到平均情况归约”的威力：它意味着 LWE 不存在”弱实例”——除非所有格问题都是容易的，否则随机 LWE 实例就是安全的。

更精确地，Regev 的核心定理可以表述为：如果存在一个算法能够高效解决随机生成的 LWE 实例（平均情况），那么就存在一个量子算法能够高效解决任何给定格上的间隙最短向量问题 GapSVP\(_\gamma\)（最坏情况）。归约的逻辑链条如下：

1. 起点：假设存在一个 LWE 求解器 \(\mathcal{A}\)，它能在多项式时间内以不可忽略的概率恢复秘密 \(s\)。
2. 量子步骤——离散高斯采样：Regev 构造了一个量子过程，利用高斯叠加态（Gaussian superposition）在格的对偶格上生成接近均匀的离散高斯采样。这一步是不可替代的量子操作——它将格上的几何结构转化为 LWE 实例的代数形式。
3. 经典归约：一旦获得了高质量的离散高斯采样，就可以构造出符合 LWE 分布的样本 \((A, b = As + e)\)，然后调用 \(\mathcal{A}\) 恢复 \(s\)。
4. 终点：通过反复调用上述过程，可以逐步缩短格中的向量，最终求解 GapSVP。

离散高斯采样：归约的核心洞见。 上述第 2 步中的离散高斯采样是整个归约中最精妙的构造。其本质是：给定一个格 \(L\) 和一个宽度参数 \(r\)，在格点上采样一个服从离散高斯分布 \(D_{L,r}\) 的向量——即每个格点 \(\mathbf{v}\) 被选中的概率正比于 \(\exp(-\pi \|\mathbf{v}\|^2 / r^2)\)。Regev 证明，如果我们能高效地在对偶格 \(L^*\) 上做这种采样，就可以将格上的”几何问题”（找短向量）转化为”代数问题”（解线性方程加噪声），而后者正是 LWE。这一构造之所以需要量子计算，是因为经典方法在格维度 \(n\) 较大时无法高效地从短向量描述中生成离散高斯分布——量子叠加态提供了一条捷径。

这一归约的近似因子为 \(\tilde{O}(n / \alpha)\)，其中 \(\alpha\) 是 LWE 噪声与模数 \(q\) 的比率，\(n\) 是格的维度。对于密码学应用中的典型参数（\(\alpha \approx 1/\sqrt{n}\)），近似因子约为 \(\tilde{O}(n^{1.5})\)。这意味着攻破 LWE 的难度不低于求解维度 \(n\) 格上近似因子为 \(\tilde{O}(n^{1.5})\) 的 GapSVP——而后者被认为对经典和量子计算机都是指数级困难的。

为什么这给了我们信心。 Regev 归约赋予 LWE 一种独特的安全论证：与 RSA（其安全性基于因子分解的猜想困难性，没有最坏-平均情况联系）不同，LWE 的安全性锚定在格问题的最坏情况困难性上。这意味着：（1）攻击者不能指望碰到”容易”的 LWE 实例——每一个随机实例都至少和最难的格问题一样难；（2）格上近似 SVP 经过了数十年的密码分析，已知最优算法（格筛法、BKZ 系列）的复杂度仍然是指数级的，Shor 算法对其无效；（3）即使归约本身使用了量子步骤，被归约的困难问题（GapSVP）的困难性假设同时涵盖经典和量子攻击者。这三点结合起来，使得 LWE 成为后量子密码学中理论根基最坚实的困难假设之一。

Peikert 在 2009 年进一步给出了纯经典（非量子）版本的归约，但代价是近似因子略有增大。后续的 MLWE 归约（Langlois 和 Stehlé，2015）将这一思路推广到模格设定，证明 MLWE 的困难性可归约到模格上的近似 SVP。ML-KEM 和 ML-DSA 的安全性最终锚定在这条归约链的起点——格上近似 SVP 的最坏情况困难性。

Ring-LWE 与 Module-LWE

原始 LWE 的公钥尺寸为 O(n^2)，在实际参数下过于庞大。为缩小密钥尺寸，学者们引入了代数结构。环上带误差学习问题（Ring-LWE）将矩阵替换为分圆多项式环 R_q = Z_q[x]/(x^n + 1) 中的单个元素，公钥尺寸降至 O(n)，但也带来了额外的代数结构——攻击者可能利用环的特殊性质（如理想格的子结构）发起针对性攻击。

模格上带误差学习问题（Module-LWE, MLWE）在 LWE 和 Ring-LWE 之间取得了精巧的平衡。MLWE 在 R_q 上定义一个 k×k 的矩阵 A，秘密和误差均为 R_q^k 中的向量。当 k = 1 时退化为 Ring-LWE；当多项式次数 n = 1 时退化为标准 LWE。通过调节 k 和 n 两个维度，MLWE 既保留了环结构带来的高效多项式乘法，又因为 k > 1 的矩阵结构稀释了环的代数特殊性，在实践中被认为比纯 Ring-LWE 更为保守。NIST 最终选定的 ML-KEM 和 ML-DSA 都建立在 MLWE 之上，多项式次数固定为 n = 256，模数 q = 3329（ML-KEM）或 q = 8380417（ML-DSA），通过 k = 2, 3, 4 的选取提供不同安全级别。

理想格的结构性攻击风险与争议

Ring-LWE 和 Module-LWE 的效率优势来源于多项式环 \(R_q = \mathbb{Z}_q[X]/(X^n + 1)\) 的代数结构——环中的乘法对应系数向量的循环卷积（准确地说是负包络卷积），可以用 NTT 在 \(O(n \log n)\) 内完成。但这一结构同时意味着，RLWE/MLWE 对应的格不是一般格，而是理想格（ideal lattice）或模格（module lattice）：它们是数域 \(\mathbb{Q}(\zeta_{2n})\) 的整数环 \(\mathcal{O}_K\) 中理想（或有限生成模）所对应的格，具有额外的代数对称性。这一对称性是否可被攻击者利用，是格基密码学中最具争议的开放问题之一。

已知的结构性攻击。 Cramer、Ducas、Peikert 和 Regev 在 2016 年证明了一个关键结果：在主理想格（principal ideal lattice）上，给定理想的 \(\mathbb{Z}\)-基，可以在量子多项式时间内恢复一个短生成元——即求解一类受限的 SVP。该攻击分两步：第一步利用量子算法求解主理想问题（Principal Ideal Problem），将 \(\mathbb{Z}\)-基转化为生成元表示；第二步利用对数嵌入（log-embedding）在对数空间中找到短生成元。这一结果直接导致了基于主理想格的 Soliloquy 方案被撤回，并迫使 NTRU 类方案的参数选择更加保守。

此外，还有若干针对理想格的结构性攻击路径值得关注：（1）子格攻击（sublattice attack）——理想格中的子理想对应子格，攻击者可能通过分析理想的因式分解结构，在低维子格上求解 SVP 后提升到全格。Albrecht 和 Lee（2021）的工作表明，对于某些特殊的分圆域，子格攻击可以提供常数因子的加速，但不改变渐近指数复杂度；（2）量子代数攻击——超越 Cramer 等人的主理想攻击，Biasse、Fieker 和 Song 等人研究了利用量子算法求解一般（非主）理想格上 SVP 的可能性。目前的结论是，对于 \(2\) 的幂次分圆域（即 ML-KEM 和 ML-DSA 使用的 \(X^n + 1\) 域），尚未发现比一般格 SVP 算法更优的量子攻击，但对于某些导子较大的分圆域已存在亚指数攻击（Cramer 等人，2017），这提示环的选择至关重要。

MLWE 比 RLWE 更保守的理由。 MLWE 被认为比纯 RLWE 更为保守，核心原因在于代数结构的”稀释”。在 RLWE 中，整个方案的安全性依赖于单个多项式环元素的困难性——对应一个 \(n\) 维理想格上的 SVP。而在 MLWE 中，秘密和误差是 \(k\) 个环元素组成的向量，对应的格是 \(R_q^k\) 中的模格——一个 \(kn\) 维的格，其结构比单个理想格更接近一般格。具体来说：（1）模格不是单个理想，而是理想的直和，攻击者无法直接利用主理想分解技术；（2）即使攻击者能在单个 \(n\) 维理想格上获得某种代数加速，面对 \(kn\) 维模格时，这一加速需要推广到模结构上——目前没有已知方法能做到这一点；（3）当 \(k\) 增大时，MLWE 的困难性在理论上单调递增，最终趋近于标准 LWE——这为参数选择提供了一个可调节的”保守程度旋钮”。

持续争议。 尽管如此，部分密码学家（如 Daniel Bernstein）对理想格的长期安全性持更谨慎的立场，理由是：（1）代数数论工具仍在快速发展，未来可能出现新的结构性攻击；（2）目前的安全评估（如 Lattice Estimator）并未完整建模所有可能的代数攻击路径；（3）安全归约中存在”间隙”——MLWE 的困难性归约到理想格 SVP，而非一般格 SVP，归约的紧密度也存在损失。这一争议的实际影响体现在参数选择策略上：ML-KEM 的参数留有约 20-30 比特的安全余量（上述 ML-KEM-768 的经典安全性估计为 183-193 比特，远高于 Level 3 所需的 143 比特），部分原因正是为了应对理想格结构可能带来的尚未发现的加速。

二、ML-KEM 算法结构

ML-KEM 是一个密钥封装机制（Key-Encapsulation Mechanism, KEM），其功能是在两个通信方之间协商一个共享密钥（Shared Secret）。与传统的公钥加密不同，KEM 不直接加密任意消息，而是封装一个随机产生的密钥——这一设计范式大幅简化了安全性证明，并天然适配混合加密（Hybrid Encryption）的使用场景。

参数集

ML-KEM 定义了三个参数集，分别对应 NIST 后量子安全级别 1、3、5。以下表格汇总了完整的算法参数、输出尺寸与安全性估计（安全估计来源为 Lattice Estimator 2024 年校准版本）：

其中 \(k\) 决定模格的模块维度，\(\eta_1\) 和 \(\eta_2\) 分别控制密钥生成和加密阶段的噪声幅度（采用中心二项分布 \(\text{CBD}_\eta\)），\(d_u\) 和 \(d_v\) 是压缩参数。所有参数集的底层多项式环均为 \(R_q = \mathbb{Z}_q[X]/(X^{256} + 1)\)，\(q = 3329\)。解密失败概率是指合法生成的密文在解封装时恢复出错误消息的概率——该概率必须远低于 \(2^{-128}\)，否则攻击者可通过构造大量密文触发失败事件来提取密钥信息（D’Anvers 等人的失败提升攻击）。

KeyGen（密钥生成）

密钥生成算法 ML-KEM.KeyGen() 的执行过程如下：

1. 采样一个 32 字节的随机种子 d，以及一个 32 字节的随机值 z（用于隐式拒绝）。
2. 利用可扩展输出函数（XOF，基于 SHAKE-128）从种子 d 确定性地生成 k×k 的矩阵 Â（在 NTT 域中表示）。
3. 采样 k 个秘密多项式 s_i 和 k 个误差多项式 e_i，各系数服从 CBD_η₁ 分布。
4. 计算 ŝ = NTT(s) 和 ê = NTT(e)，然后在 NTT 域中计算 t̂ = Â ◦ ŝ + ê。
5. 公钥 ek = (t̂, ρ)（其中 ρ 是生成 Â 的种子），解密密钥 dk = (ŝ, ek, H(ek), z)。

这里有一个重要的设计细节：矩阵 Â 本身并不存储在公钥中，而是通过种子 ρ 在使用时即时生成。这一策略将公钥中矩阵的存储开销从 k^2 · n · ⌈log q⌉ 位压缩至仅 256 位，是 ML-KEM 密钥尺寸远小于标准 LWE 方案的关键原因之一。

Encaps（封装）

封装算法 ML-KEM.Encaps(ek) 的执行过程如下：

1. 采样一个 32 字节的随机消息 m。
2. 计算 (K, r) = G(m ‖ H(ek))，其中 G 是基于 SHA3-512 的哈希函数，K 是最终共享密钥，r 是确定性随机性。
3. 使用 r 作为随机性执行内部 CPA 加密：采样向量 r、e₁ 和标量 e₂（噪声分量），计算密文 (u, v)。
4. 具体地，u = NTT⁻¹(Â^T ◦ NTT(r)) + e₁，v = NTT⁻¹(t̂^T ◦ NTT(r)) + e₂ + ⌈q/2⌋ · m。
5. 对 u 和 v 分别进行 d_u 位和 d_v 位的压缩，输出密文 c = (Compress(u), Compress(v))。
6. 返回 (K, c)。

压缩操作 Compress_d(x) = ⌊(2^d / q) · x⌉ mod 2^d 是一种有损量化：它将 Z_q 中的元素映射到 d 位整数空间，在丢弃低位信息的同时大幅缩减密文体积。解压操作 Decompress_d(x) = ⌊(q / 2^d) · x⌉ 则执行反向映射，但无法完全恢复原值——产生的量化噪声需要被解密过程中的纠错余量所吸收。

Decaps（解封装）

解封装算法 ML-KEM.Decaps(dk, c) 的执行过程如下：

1. 对密文 c 进行解压，恢复近似的 u’ 和 v’。
2. 计算 m’ = Compress_1(v’ - NTT⁻¹(ŝ^T ◦ NTT(u’)))。这一步的本质是：v’ 中包含 t^T · r + e₂ + ⌈q/2⌋ · m 的近似值，而 s^T · u’ 近似于 s^T · A^T · r + s^T · e₁ = t^T · r - e^T · r + s^T · e₁，两者相减后噪声项被大幅抵消，⌈q/2⌋ · m 的信号被保留——只要总噪声不超过 ⌊q/4⌋，1 位压缩即可正确恢复 m 的每一个系数。
3. 利用恢复出的 m’ 重新执行封装过程（重新加密），得到密文 c’。
4. 若 c’ = c，则输出 K = G(m’ ‖ H(ek))；否则输出 K’ = J(z ‖ c)（隐式拒绝，详见第四节）。

解密正确性的核心在于噪声预算（Noise Budget）：所有噪声分量（秘密-误差交叉项 e^T · r、s^T · e₁、e₂、以及压缩/解压引入的量化误差）的叠加绝对值必须小于 ⌊q/4⌋ ≈ 832。ML-KEM 的参数选择确保了解密失败概率极低——ML-KEM-768 的失败概率约为 2^(-164)，远低于安全性所需的上界。

三、ML-KEM 的核心运算

基于 NTT 的多项式乘法

ML-KEM 中最频繁且计算量最大的操作是 R_q 中的多项式乘法。朴素的多项式乘法需要 O(n^2) 次系数乘法，而数论变换（Number Theoretic Transform, NTT）将其降至 O(n log n)。

NTT 是离散傅里叶变换（DFT）在有限域 Z_q 上的类比。它利用了 ML-KEM 参数中一个精心选择的性质：q = 3329 = 13 · 256 + 1，使得 Z_q 中存在 256 阶本原单位根。这意味着多项式环 R_q = Z_q[x]/(x^256 + 1) 可以通过 NTT 完全分裂为 128 个形如 Z_q[x]/(x^2 - ζ^(2i+1)) 的二次因子的直积。

在实现中，ML-KEM 的 NTT 不是将多项式变换为 256 个点值，而是变换为 128 对系数——每对系数对应一个二次因子 Z_q[x]/(x^2 - ζ^(2i+1)) 中的元素。NTT 域中的”逐点乘法”实际上是 128 次二次多项式的模乘（每次涉及 4 次系数乘法和 2 次加法）。这种设计避免了需要 512 阶单位根（q - 1 = 3328 = 2^6 · 52 并不含 512 的因子），同时仍然提供了优异的运算效率。

以下是简化的 NTT 正变换和基于 NTT 的多项式乘法的 Python 实现：

# 简化的 NTT 实现（用于 ML-KEM / Kyber 的多项式乘法）
# q = 3329, n = 256, 使用 Montgomery 风格的蝶形运算

Q = 3329
N = 256

# 预计算的 NTT 旋转因子（zetas），ζ = 17 是 Z_q 中的 256 阶本原单位根
ZETAS = [1]
zeta = 17
for i in range(1, 128):
    ZETAS.append(ZETAS[-1] * zeta % Q)

def ntt(f):
    """将多项式 f（长度 256 的系数列表）变换到 NTT 域。"""
    a = list(f)
    k = 1
    length = 128
    while length >= 2:
        start = 0
        while start < N:
            z = ZETAS[k]
            k += 1
            for j in range(start, start + length):
                t = z * a[j + length] % Q
                a[j + length] = (a[j] - t) % Q
                a[j] = (a[j] + t) % Q
            start += 2 * length
        length //= 2
    return a

def inv_ntt(f):
    """将 NTT 域表示的多项式变换回系数域。"""
    a = list(f)
    k = 127
    length = 2
    while length <= 128:
        start = 0
        while start < N:
            z = ZETAS[k]
            k -= 1
            for j in range(start, start + length):
                t = a[j]
                a[j] = (t + a[j + length]) % Q
                a[j + length] = (z * (a[j + length] - t)) % Q
            start += 2 * length
        length *= 2
    inv_n = pow(128, Q - 2, Q)  # 128 的模逆元
    return [(x * inv_n) % Q for x in a]

def basemul(a0, a1, b0, b1, zeta_power):
    """NTT 域中一对系数的基乘法（对应 Z_q[x]/(x^2 - ζ) 中的乘法）。"""
    c0 = (a0 * b0 + a1 * b1 * zeta_power) % Q
    c1 = (a0 * b1 + a1 * b0) % Q
    return c0, c1

def poly_mul_ntt(f, g):
    """利用 NTT 计算两个多项式在 R_q = Z_q[x]/(x^256+1) 中的乘积。"""
    f_hat = ntt(f)
    g_hat = ntt(g)
    h_hat = [0] * N
    for i in range(64):
        z = ZETAS[64 + i]
        # 偶数组
        h_hat[4*i], h_hat[4*i+1] = basemul(
            f_hat[4*i], f_hat[4*i+1],
            g_hat[4*i], g_hat[4*i+1], z)
        # 奇数组
        h_hat[4*i+2], h_hat[4*i+3] = basemul(
            f_hat[4*i+2], f_hat[4*i+3],
            g_hat[4*i+2], g_hat[4*i+3], Q - z)
    return inv_ntt(h_hat)

压缩与解压

压缩操作将 Z_q 中的系数量化到较少位数，是 ML-KEM 控制密文尺寸的核心手段。对于 d 位压缩，Compress_d(x) = ⌊(2^d / q) · x + 1/2⌋ mod 2^d，解压 Decompress_d(y) = ⌊(q / 2^d) · y + 1/2⌋。量化引入的最大误差不超过 ⌈q / 2^(d+1)⌉。对于 ML-KEM-768 中 d_u = 10 的设置，u 向量的每个系数的量化误差上界为 ⌈3329 / 2048⌉ = 2，这一精度在噪声预算中是可以承受的。

噪声采样

ML-KEM 使用中心二项分布（Centered Binomial Distribution, CBD）而非离散高斯分布来采样噪声。CBD_η 的定义为：采样 2η 个独立均匀比特 (a_1, …, a_η, b_1, …, b_η)，输出 Σa_i - Σb_i。CBD 的输出范围为 [-η, η]，其方差为 η/2。选择 CBD 而非高斯分布的关键理由是：CBD 的采样仅涉及随机比特的异或和计数操作，天然免疫时序侧信道——不存在依赖于采样值的条件分支或浮点运算。

四、Fujisaki-Okamoto 变换在 ML-KEM 中的应用

从 CPA 安全到 CCA 安全

ML-KEM 的内核是一个 IND-CPA 安全的公钥加密方案（PKE）：攻击者无法区分同一公钥下两条不同消息的密文。然而，在实际应用中，我们需要更强的 IND-CCA2 安全性（Indistinguishability under Adaptive Chosen-Ciphertext Attack）——攻击者即使拥有解密预言机，也无法获取关于目标密文的任何信息。CPA 安全到 CCA 安全之间的鸿沟是巨大的：CPA 安全的方案可能在面对密文篡改时完全崩溃。

Fujisaki-Okamoto（FO）变换是弥合这一鸿沟的经典工具。其核心思想优雅而简洁：在封装时，使用消息 m 的哈希值作为加密随机性——这使得加密过程变为确定性的；在解封装时，先解密恢复 m’，再用 m’ 重新加密，将得到的密文与收到的密文进行比对。若一致，说明密文确实由合法封装过程产生，输出正确的共享密钥；若不一致，则密文遭到了篡改。

隐式拒绝

ML-KEM 中的 FO 变换采用了隐式拒绝（Implicit Rejection）策略：当重新加密校验失败时，算法不会返回错误标志，而是输出一个伪随机的密钥 K’ = J(z ‖ c)，其中 z 是解密密钥中保存的随机值，c 是收到的密文。攻击者无法区分 K’ 与合法密钥——因为 J 是一个伪随机函数（基于 SHAKE-256），且 z 对攻击者完全保密。

隐式拒绝的安全意义是深远的。显式拒绝（返回 ⊥）会向攻击者泄漏一比特信息——“你提交的密文无效”——在某些场景下，攻击者可以利用这一比特的反馈逐步提取秘密密钥（类似于 Bleichenbacher 对 RSA PKCS#1 v1.5 的著名攻击）。隐式拒绝从根本上封堵了这条信息泄漏通道：无论攻击者提交什么密文，他总是会得到一个看起来合法的密钥，但这个密钥除了对该特定密文以外不包含任何有用信息。

安全性归约

经过 FO 变换后，ML-KEM 的 IND-CCA2 安全性可以紧致地归约到底层 CPA-PKE 的 IND-CPA 安全性，以及所使用的哈希函数 G、H、J 在随机预言机模型（Random Oracle Model, ROM）中的安全性。具体来说，任何对 ML-KEM 的 CCA 攻击者 A，都可以被转化为一个对底层 CPA-PKE 的 CPA 攻击者 B，使得 B 的优势与 A 的优势仅相差可忽略的量。在量子随机预言机模型（QROM）中，Kuchta 等人的工作进一步证明了类似的紧致归约，确保了 ML-KEM 在量子攻击者面前的安全性。

五、ML-DSA 算法结构

ML-DSA 是一个数字签名方案，其安全性同样基于 MLWE 问题，但采用了与 ML-KEM 截然不同的构造范式——Fiat-Shamir with Aborts。

参数集

ML-DSA 定义了三个参数集：

其中 q = 8380417 = 2^23 - 2^13 + 1，多项式次数 n = 256。这个模数的选择同样是精心设计的：q ≡ 1 (mod 512)，使得 Z_q 中存在 512 阶本原单位根，NTT 可以将 R_q 完全分裂为 256 个一次因子的直积（与 ML-KEM 的 128 个二次因子不同）。

KeyGen（密钥生成）

1. 采样随机种子 ξ（32 字节）。
2. 从 ξ 确定性地生成矩阵 Â ∈ R_q^{k×l}（NTT 域）。
3. 采样秘密向量 s₁ ∈ R_q^l 和 s₂ ∈ R_q^k，各系数均匀分布在 [-η, η]。
4. 计算 t = As₁ + s₂。
5. 将 t 分解为高位 t₁ 和低位 t₀：t = t₁ · 2^d + t₀。
6. 公钥 pk = (ρ, t₁)，秘密密钥 sk = (ρ, K, tr, s₁, s₂, t₀)，其中 tr = H(pk)。

Sign（签名）

签名算法是 ML-DSA 最复杂的部分，其核心是一个拒绝采样（Rejection Sampling）循环：

1. 计算消息哈希 μ = H(tr ‖ M)。
2. 初始化计数器 κ = 0。
3. 循环开始：采样掩码向量 y ∈ R_q^l，每个系数均匀分布在 [-γ₁ + 1, γ₁]。
4. 计算 w = Ay。
5. 将 w 的每个系数分解为高位 w₁ 和低位 w₀。
6. 计算挑战哈希 c̃ = H(μ ‖ w₁)，然后从 c̃ 确定性地导出挑战多项式 c ∈ R_q（恰好有 τ 个系数为 ±1，其余为零）。
7. 计算 z = y + c · s₁。
8. 拒绝检查：若 z 的任一系数的绝对值 ≥ γ₁ - β，或者 w - c · s₂ 的低位部分的任一系数绝对值 ≥ γ₂ - β，则递增 κ，回到步骤 3 重新采样。
9. 计算提示向量 h（Hint Vector），用于帮助验证者在不知道 s₂ 的情况下从 Az - ct 的高位恢复 w₁。
10. 若 h 中非零元素个数超过上界 ω，同样拒绝并重试。
11. 输出签名 σ = (c̃, z, h)。

Verify（验证）

1. 从公钥恢复 Â 和 t₁。
2. 计算 μ = H(tr ‖ M)。
3. 从 c̃ 导出挑战多项式 c。
4. 计算 w’ = Az - c · t₁ · 2^d。
5. 利用提示向量 h 从 w’ 恢复 w₁’。
6. 验证 c̃ = H(μ ‖ w₁’) 且 z 的系数均满足范围约束。

验证过程的计算量远小于签名——不需要拒绝采样循环，只需一次矩阵-向量乘法和一次哈希比对。

六、ML-DSA 的 Fiat-Shamir with Aborts

为什么需要拒绝采样

ML-DSA 的签名过程中，z = y + c · s₁ 这一步会在 z 中泄漏关于秘密 s₁ 的信息：如果攻击者收集足够多的签名 (c_i, z_i)，就可以通过统计分析估计出 c_i · s₁ 的均值，进而恢复 s₁。拒绝采样（Rejection Sampling）正是为了消除这一信息泄漏：只有当 z 的分布”看起来”与 y 的原始分布（在 [-γ₁ + 1, γ₁] 上的均匀分布）足够接近时，签名才被接受并输出。具体地，如果 z 的某个系数因 c · s₁ 的叠加而偏移到了 [-γ₁ + 1, γ₁] 范围之外或接近边界，就触发拒绝。

从概率论的角度看，这一过程可以用 Lyubashevsky 的离散拒绝采样引理来严格分析：经过拒绝采样后，输出的 z 的统计分布与不依赖于 s₁ 的参考分布之间的统计距离是可忽略的。代价是签名需要平均重复若干次才能成功——对于 ML-DSA-65，平均迭代次数约为 5.1 次。

挑战生成

挑战多项式 c 是 Fiat-Shamir 范式的核心组件：它将交互式证明中验证者的随机挑战替换为对消息和承诺（w₁）的哈希值。c 被约束为恰好有 τ 个非零系数（均为 ±1），这一稀疏结构确保了 c · s₁ 的系数幅度可控——每个系数的绝对值至多为 τ · η = β。这一上界 β 直接进入拒绝采样的判定条件，也是安全参数设计的关键约束。

提示向量

提示向量 h 是 ML-DSA 中一个精巧的工程设计。在验证过程中，验证者需要恢复签名时 w = Ay 的高位 w₁，但验证者只能计算 Az - ct = A(y + cs₁) - ct = Ay + c(As₁ - t) = Ay - cs₂，即 w - cs₂。由于 cs₂ 的低位分量可能导致 w - cs₂ 与 w 的高位函数产生不同的进位（类似十进制中 49 + 2 = 51 改变了十位），提示向量 h 精确记录了哪些系数位置发生了这种进位，使验证者能正确恢复 w₁。h 是一个二元向量（仅含 0 和 1），其非零元素个数由签名参数 ω 上界——这一约束限制了签名尺寸，同时也是安全性分析的一部分。

七、安全性分析

Core-SVP 困难性

ML-KEM 和 ML-DSA 的安全性最终归约到 MLWE 问题的困难性，而 MLWE 的困难性又与格上近似 SVP 的困难性紧密相关。密码学界通常使用 core-SVP（或称 BKZ cost model）来估计格攻击的计算成本：假设攻击者使用 BKZ-β 算法（目前最优的格基约简算法族）来求解 SVP，则所需的经典计算量约为 2^{0.292β}，量子计算量约为 2^{0.265β}（使用 Grover 加速的格筛法）。

对于 ML-KEM-768，对应的 MLWE 实例的格维度为 d = k · n = 768，BKZ 块维度 β 约为 630 至 660（取决于具体的攻击策略和估计模型），对应的经典 core-SVP 安全级别约为 183 至 193 比特，量子 core-SVP 安全级别约为 166 至 175 比特。这些数值高于 NIST Level 3 所要求的 AES-192 等价安全级别（143 比特量子安全性）。

格估计器

NIST 后量子密码标准化过程中广泛使用了格估计器（Lattice Estimator，由 Martin Albrecht 等人开发维护的开源工具）来评估 MLWE/MLWR 参数的具体安全强度。格估计器综合考虑了所有已知的格攻击策略——包括原始攻击（Primal Attack）、对偶攻击（Dual Attack）、混合攻击（Hybrid Attack）以及针对环/模结构的特殊攻击——并输出每种攻击的预估计算成本。值得注意的是，2023 年 Ducas 和 van Woerden 对对偶攻击中”几何级数假设”（Geometric Series Assumption）的修正，使得部分旧的安全估计需要重新评估，但 ML-KEM 和 ML-DSA 的参数选择留有足够的安全余量，修正后的估计仍然满足目标安全级别。

侧信道考量

格基方案的侧信道安全性是工程部署中的重要考量。ML-KEM 的解封装过程涉及秘密密钥 ŝ 与密文的乘法运算，若实现不当，可能通过功耗分析（Power Analysis）或电磁辐射分析泄漏密钥信息。ML-DSA 的签名过程中，拒绝采样的循环次数本身就是一个潜在的时序侧信道——如果攻击者能测量签名耗时，就可能推断出与秘密相关的信息。FIPS 203 和 FIPS 204 标准文本明确要求所有实现必须使用常量时间（Constant-Time）操作，禁止依赖于秘密数据的条件分支和内存访问模式。此外，ML-KEM 的隐式拒绝机制也要求解封装的两条执行路径（校验成功和校验失败）在时间和功耗特征上不可区分。

八、实现优化

NTT 实现

NTT 是 ML-KEM 和 ML-DSA 中计算占比最高的操作（在 ML-KEM 的封装和解封装中占总计算量的 60% 至 70%）。高效实现的关键在于：

Barrett/Montgomery 模约简。 Z_q 中的乘法后需要对 q 取模，整数除法是昂贵的操作。Barrett 约简通过预计算 q 的倒数的定点近似值，将除法转换为乘法和移位；Montgomery 约简则通过选择一个 2 的幂次 R（通常 R = 2^16），将模运算转化为关于 R 的运算，避免了除法。ML-KEM 的参考实现中大量使用 Montgomery 约简，因为 NTT 蝶形运算中的乘法天然适配 Montgomery 形式。

蝶形运算的排列。 Cooley-Tukey 型（用于正向 NTT）和 Gentleman-Sande 型（用于逆向 NTT）蝶形运算的选择影响数据访问模式和旋转因子的预计算方式。ML-KEM 参考实现采用 Cooley-Tukey 正向变换和 Gentleman-Sande 逆向变换的组合，以确保输入和输出都是自然顺序（避免位逆序排列的开销）。

AVX2/NEON 向量化加速

在 x86-64 平台上，AVX2 指令集提供 256 位宽的 SIMD 寄存器，可以同时处理 16 个 16 位整数。ML-KEM 的系数宽度（12 位用于未压缩值，小于 16 位）恰好可以打包到 16 位通道中。Peter Schwabe 和 Roberto Avanzi 等人的 AVX2 优化实现展示了惊人的性能：ML-KEM-768 的完整封装操作（KeyGen + Encaps）在现代 x86-64 处理器上仅需约 20 万时钟周期，解封装约 22 万时钟周期——与 X25519 椭圆曲线 Diffie-Hellman 在同一数量级。

在 ARM 平台上，NEON 指令集提供 128 位宽的 SIMD 寄存器，可同时处理 8 个 16 位整数。虽然向量宽度是 AVX2 的一半，但 ARM 处理器通常有更多的 NEON 流水线单元。在 Apple M 系列和 AWS Graviton 等高端 ARM 处理器上，ML-KEM-768 的性能表现同样优异。

常量时间要求

常量时间实现的核心原则是：所有依赖于秘密数据的操作必须使用位运算（AND、OR、XOR、移位）而非条件分支来实现。具体到 ML-KEM 和 ML-DSA 的实现中，以下操作需要特别注意：

• 比较操作（如 FO 变换中的密文比对）必须使用逐字节异或后求或的方式，而非 memcmp（后者可能在发现第一个不同字节时提前返回）。
• CBD 采样中的求和操作应使用查表或 popcount 指令，避免循环计数。
• ML-DSA 签名中的拒绝采样条件判断必须确保无论是否拒绝，执行路径的时间特征一致——通常通过”先计算两种结果，再用常量时间选择掩码选取”的模式实现。

内存占用

对于资源受限的嵌入式平台（如 ARM Cortex-M4），内存占用是关键约束。ML-KEM-768 的参考实现的栈空间需求约为 2.5 KB（不含公钥/密钥存储），这一数值对于主流微控制器来说是可接受的。优化策略包括：在线生成矩阵 Â 的各行（逐行流式生成，避免同时存储整个矩阵）；将 NTT 变换与采样操作交错进行以复用缓冲区；使用压缩格式存储秘密密钥。pqm4 项目（ARM Cortex-M4 上的后量子密码库）是这一领域的标杆实现。

ML-KEM 与 ML-DSA 参数速查表

在进入部署讨论之前，以下速查表汇总了 ML-KEM 三个参数集和 ML-DSA 三个参数集的密钥尺寸、密文/签名尺寸与性能数据（性能数据基于 Intel Core i7-13700K + AVX2 优化实现）：

ML-KEM（FIPS 203）——密钥封装机制

ML-DSA（FIPS 204）——数字签名算法

与经典方案的尺寸对比

审视这张速查表，一个结论是清晰的：从经典密码到后量子密码，密钥和签名尺寸的膨胀是真实的——ML-KEM-768 的公钥是 X25519 的 37 倍，ML-DSA-65 的签名是 Ed25519 的 51 倍——但对于绝大多数现代网络应用而言，这个增幅完全在可承受范围内。一个 TLS 握手多传输 1 到 2 KB 的数据，在宽带网络上几乎无感。然而，当你把视线转向资源受限的物联网设备——比如一个只有 16 KB RAM、通过 LoRa 以 0.3 kbps 速率通信的传感器节点——这些”可以忽略”的额外字节就成了不可逾越的障碍。后量子迁移的真正挑战，不在数据中心里那些有充裕带宽和算力的服务器上，而在网络边缘那些最脆弱、最难升级、却往往部署周期最长的设备上。

跨安全级别参数与安全裕度对照

下表综合 ML-KEM 和 ML-DSA 在三个 NIST 安全级别下的核心参数、估计安全强度和安全裕度，为工程选型提供统一视图。安全估计来源为 Lattice Estimator（2024 年校准版本），同时列出经典和量子攻击的 core-SVP 比特数。

选型决策框架：对于大多数互联网应用（TLS、SSH、信号协议），ML-KEM-768 + ML-DSA-65（Level 3）是推荐组合——安全裕度充足（约 23-32 比特），性能和尺寸开销适中。ML-KEM-512（Level 1）的量子安全裕度接近零甚至为负，仅适用于短期保护或资源极度受限的场景。ML-KEM-1024（Level 5）提供了极高的安全余量，但尺寸和计算开销约为 Level 3 的 1.3-1.5 倍，适用于需要数十年保护的档案级加密或政府/军事场景。

九、部署现状

浏览器与 CDN 的混合 KEM

2023 年 8 月，Google Chrome 浏览器在 TLS 1.3 握手中实验性地启用了 X25519Kyber768Draft 混合密钥交换——将传统的 X25519 椭圆曲线 Diffie-Hellman 与 ML-KEM-768 组合使用。混合方案的设计理念是”双保险”：即使格基方案在未来被发现有未预见的弱点，X25519 仍然提供传统安全性；反之，即使大规模量子计算机问世，ML-KEM-768 仍然提供后量子安全性。Cloudflare 同步在其全球边缘网络上部署了对该混合方案的支持，使得数以亿计的 TLS 连接开始享受后量子保护。2024 年标准正式发布后，Chrome 已过渡到基于最终标准的 X25519MLKEM768 组合。

实际测试数据显示，混合 KEM 对 TLS 握手延迟的影响微乎其微。ML-KEM-768 的公钥（1184 字节）和密文（1088 字节）虽然比 X25519 的 32 字节大得多，但在现代网络环境下，这些额外字节几乎不增加可感知的延迟。Google 的大规模 A/B 测试表明，启用混合 KEM 后，TLS 握手的 P50 延迟增加不到 0.5 毫秒。

云服务集成

AWS Key Management Service（KMS）于 2024 年宣布支持后量子 TLS，使得客户与 KMS 之间的通信可以受到后量子密钥交换的保护。Signal 通信协议在 2023 年引入了 PQXDH（Post-Quantum Extended Diffie-Hellman）密钥协商机制，将 ML-KEM-768 与 X25519 组合，为端到端加密通信提供后量子安全的前向保密性。Apple 的 iMessage 在 2024 年的 PQ3 协议升级中同样采用了类似的混合方案。

开源生态

Open Quantum Safe（OQS）项目维护的 liboqs 库提供了 ML-KEM 和 ML-DSA 所有参数集的 C 语言参考实现和优化实现，并通过 oqs-provider 集成到 OpenSSL 3.x 中，使得现有基于 OpenSSL 的应用程序可以通过简单的配置变更启用后量子算法。此外，BoringSSL（Google 维护的 OpenSSL 分支）、AWS-LC（Amazon 维护的密码库）和 wolfSSL 等主流密码库均已原生支持 ML-KEM。

在编程语言层面，Go 1.23 在其标准库 crypto/mlkem 中加入了 ML-KEM 的实现；Rust 生态中的 pqcrypto 和 ml-kem crate 提供了高质量的实现；Java 的 Bouncy Castle 库同样在 2024 年加入了 FIPS 203/204 支持。

性能基准

在 Intel Core i7-13700K 处理器上（AVX2 优化实现），ML-KEM-768 的典型性能数据如下：

作为对比，RSA-2048 的密钥生成需要数百万个时钟周期，ECDH P-256 的密钥交换约需 300,000 个时钟周期。ML-KEM 在计算性能上已经具备明显优势，其主要代价是密钥和密文尺寸的增加——但如前文所述，在现代网络环境中，这一代价是完全可以承受的。

ML-DSA-65 的签名性能因拒绝采样的随机性而存在波动，平均值约为 800,000 时钟周期（约 170 μs），验证约为 300,000 时钟周期（约 62 μs）。签名尺寸（3293 字节）虽然远大于 Ed25519（64 字节），但在绝大多数应用场景中不构成瓶颈。

后量子密码学的工程部署正在以前所未有的速度推进。从浏览器到消息应用，从云服务到嵌入式设备，ML-KEM 和 ML-DSA 正在逐步融入整个数字基础设施。格基密码不仅在理论上提供了对量子计算威胁的抵抗能力，更在实践中证明了其效率和可部署性——这正是 NIST 在长达八年的评估过程中所追求的目标。

笔者认为，ML-KEM（Kyber）在 NIST 竞赛中的胜出，揭示的关于工程政治学的信息不亚于关于密码学质量的信息。在决赛圈的候选方案中，NTRU 拥有更长的学术血统（1996 年提出），SABER 在某些指标上效率更高——但 Kyber 胜在它是最保守、最被充分理解的方案。它的模格结构介于标准 LWE 和环 LWE 之间，既不过度激进也不过度保守；它的参数选择留有充裕的安全余量；它的参考实现简洁、审计友好、几乎没有边界情况。这一结果对密码学标准化有深远的启示：在标准化竞赛中，“无聊”是一种优势——评审委员会更倾向于选择一个他们完全理解的方案，而非一个他们仍在研究的方案。

一个经常被忽视的观点是，后量子参数尺寸的膨胀将制造一道新的数字鸿沟。ML-KEM-768 的公钥约 1184 字节，在 TLS 握手中几乎无感——但将视线转向资源受限的物联网世界：一个只有 64KB RAM、通过 LoRa 以 0.3 kbps 速率通信的传感器节点，仅传输一次公钥就需要约 30 秒。更糟糕的是，ML-DSA-65 的签名（3293 字节）是 Ed25519（64 字节）的 51 倍，对于需要频繁验证固件签名的嵌入式设备而言，这不是渐进式的增长，而是质变。后量子迁移的真正挑战不在数据中心，而在网络边缘那些最脆弱、最难升级、部署周期却最长的设备上——这些设备很可能在量子计算机问世时仍在运行今天的经典密码。

从工程实践来看，当前普遍采用的”混合模式”（经典 + 后量子）部署策略，表面上是一种安全的过渡措施，但它实际上暴露了一个深层的认识论困境：我们对任何单一后量子假设都没有足够的信心来独立押注。格基假设（MLWE）虽然被研究了近二十年，但与 RSA 的因子分解假设或椭圆曲线的 ECDLP 假设相比，它的学术审查历史仍然年轻。混合模式的存在本身就是密码学社区对自身知识边界的一种诚实承认——这在密码学史上是罕见的。更实际地说，混合模式还揭示了一个工程权衡：它将 TLS ClientHello 的密钥份额从 32 字节膨胀到约 1250 字节，可能导致某些中间设备（防火墙、负载均衡器）因缓冲区溢出而断开连接。混合模式不是免费午餐，它是我们为认识论上的审慎所支付的工程代价。

密码学百科系列 · 第 58 篇

← 上一篇：后量子密码总览 | 系列目录 | 下一篇：哈希基签名 →