【密码学百科】格基后量子方案：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 等关键密码学构造的设计逻辑，分析安全性证明的核心假设，并探讨工程实现中的优化策略与当前的部署进展。

如果只想要结论：

按问题找相关文章：后量子密码的整体版图和五条技术路线见《后量子密码总览》；SVP、LWE 和格基约化的数学基础见《格密码数学基础》；不依赖格假设的签名备选见《哈希基签名》；系统怎么从 RSA/ECC 迁过来见《PQC 迁移工程指南》。

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

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）则要求找到格中离给定目标点最近的格向量。精确 SVP 在随机归约下是 NP 困难的（Ajtai, 1998），CVP 是 NP 困难的；但密码学实际依赖的是多项式近似因子版本，这些版本并未被证明 NP 困难（例如 \(\sqrt{n}\) 近似的 GapSVP 属于 NP ∩ coNP，Aharonov & Regev, 2005），它们的困难性来自几十年的密码分析经验。更重要的是，目前尚无已知的量子算法能对它们提供超多项式加速——Shor 算法依赖的周期查找结构在一般格问题上找不到着力点。

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

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

离散高斯采样：归约的核心洞见。 上述第 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 的最坏情况困难性。

原始 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 类方案的参数选择更加保守。

此后的推进是一般理想上的量子代数攻击：Cramer、Ducas 和 Wesolowski（EUROCRYPT 2017）把上述思路推广到分圆域中的一般（非主）理想，在量子多项式时间内求解近似因子为 \(\exp(\tilde{O}(\sqrt{n}))\) 的 Ideal-SVP，这一近似因子优于 BKZ 在同等时间内能达到的水平。需要强调它的边界：该攻击针对的是 Ideal-SVP 且近似因子是亚指数级，而 Ring-LWE / Module-LWE 的归约和实际参数对应的是多项式近似因子；到目前为止，没有已知攻击能利用这些代数结构，在 ML-KEM 和 ML-DSA 使用的 \(X^{256} + 1\) 环上比一般格算法更快地求解 MLWE。

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-768 而不是 ML-KEM-512，并在过渡期与 X25519 组成混合方案，就是为未知的结构性攻击和攻击代价估计的误差留出余量（core-SVP 估计与 NIST 安全级别的关系见第七节）。

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

ML-KEM 定义了三个参数集，分别对应 NIST 后量子安全级别 1、3、5。以下表格汇总了算法参数、输出尺寸与安全性估计。参数与尺寸取自 FIPS 203；core-SVP 一行是估计范围，下界取自 Kyber 第三轮规范，范围反映不同攻击模型和估计器版本之间的差异；解密失败概率取自 Kyber 第三轮规范：

其中 \(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 等人的失败提升攻击）。

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

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

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

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

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

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

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^8 · 13，只含 256 而不含 512 的因子），同时仍然提供了优异的运算效率。

以下是 NTT 正变换、逆变换和基于 NTT 的多项式乘法的 Python 实现，结构对应 FIPS 203 的 Algorithm 9–12。旋转因子必须按 7 位位逆序排列（第 \(i\) 项为 \(\zeta^{\mathrm{BitRev}_7(i)}\)）；如果按自然顺序取 \(\zeta^i\)，乘出来的结果是错的。这段代码用 Python 3.12 与朴素的负循环卷积（在 \(\mathbb{Z}_q[X]/(X^{256}+1)\) 中逐项相乘）对拍过，结果一致：

# ML-KEM / Kyber 的 NTT 多项式乘法（教学实现，未做常量时间与 Montgomery 优化）
# q = 3329, n = 256

Q = 3329
N = 256

def bitrev7(x):
    return int(f'{x:07b}'[::-1], 2)

# ζ = 17 是 Z_q 中的 256 阶本原单位根；ZETAS[i] = 17^BitRev7(i) mod q
ZETAS = [pow(17, bitrev7(i), Q) for i in range(128)]

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):
        # ZETAS[64+i] = ζ^(2·BitRev7(2i)+1)，第 2i+1 对取其相反数
        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 的采样仅涉及随机比特的异或和计数操作，天然免疫时序侧信道——不存在依赖于采样值的条件分支或浮点运算。

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 安全性可以在随机预言机模型（Random Oracle Model, ROM）中归约到底层 CPA-PKE 的安全性，外加一个与解密失败概率 \(\delta\) 相关的项——这也是参数表里要把解密失败概率压到 \(2^{-139}\) 以下的原因之一。模块化的分析框架来自 Hofheinz、Hövelmanns 和 Kiltz（TCC 2017）。对量子攻击者要在量子随机预言机模型（QROM）中分析，攻击者可以对哈希函数做叠加态查询：HHK17 给出了 QROM 下的归约但有明显的安全损失，此后 Jiang 等（CRYPTO 2018）、Bindel 等（TCC 2019）、Kuchta 等（EUROCRYPT 2020）逐步收紧，但 QROM 归约至今仍不是紧的。工程上的含义是：ML-KEM 的具体参数安全性依赖对底层 MLWE 的攻击代价估计，而不是依赖归约本身的紧致度。

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

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

签名尺寸以 FIPS 204 终稿为准。第三轮 Dilithium 规范中 Dilithium3 / Dilithium5 的签名是 3293 / 4595 字节，FIPS 204 把挑战哈希 \(\tilde{c}\) 的长度从固定 32 字节改为随安全级别变化（32 / 48 / 64 字节），所以 ML-DSA-65 / ML-DSA-87 分别多出 16 / 32 字节。旧资料里的 3293、4595 指的是 Dilithium，不是 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 个二次因子不同）。

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

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

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），其非零元素个数由签名参数 ω 上界——这一约束限制了签名尺寸，同时也是安全性分析的一部分。

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 比特。

这些 core-SVP 数字不能直接和 NIST 安全级别相减。NIST 在 2016 年的征集文件里用「破解 AES / 找 SHA 碰撞所需的经典门数」定义安全级别：Level 1、3、5 分别对应 AES-128、AES-192、AES-256 的密钥搜索，经典门数约为 \(2^{143}\)、\(2^{207}\)、\(2^{272}\)。core-SVP 只计一次 SVP 调用中格筛法的主导代价，不计 BKZ 需要的多轮调用、每次操作的门数和内存访问代价，是一个刻意偏保守的简化指标。所以「ML-KEM-512 的 core-SVP 只有 118 比特、低于 143」并不能直接推出它达不到 Level 1。

这正是 ML-KEM-512 曾引发公开争论的地方。Bernstein 等人批评 NIST 在估算 Kyber-512 安全性时对内存代价等因素的处理过于乐观；NIST 在第三轮状态报告（NIST IR 8413，2022）中的立场是，计入实际攻击所需的巨大内存访问代价后，Kyber-512 仍可认为达到 Level 1，但裕度不大。对需要长期保密的数据，这场争论的实际结论就是优先选 ML-KEM-768。

NIST 后量子密码标准化过程中广泛使用了格估计器（Lattice Estimator，由 Martin Albrecht 等人开发维护的开源工具）来评估 MLWE/MLWR 参数的具体安全强度。格估计器综合考虑已知的格攻击策略——原始攻击（Primal Attack）、对偶攻击（Dual Attack）、混合攻击（Hybrid Attack）等——并输出每种攻击的预估计算成本。攻击估计本身也在变化：MATZOV（2022）提出改进的对偶-筛法攻击，声称把 Kyber 各参数集的估计代价降低了若干比特；Ducas 和 Pulles（CRYPTO 2023）随后指出，这类对偶攻击依赖的统计独立性启发式在相关参数区间并不成立，其宣称的收益存疑。这场讨论说明，具体参数的安全比特数是随密码分析进展而修订的估计值，不是定理。

格基方案的侧信道安全性是工程部署中的重要考量。ML-KEM 的解封装过程涉及秘密密钥 ŝ 与密文的乘法运算，若实现不当，可能通过功耗分析（Power Analysis）或电磁辐射分析泄漏密钥信息。ML-DSA 的签名过程中，拒绝采样的循环次数会随签名变化；Dilithium 的设计分析认为循环次数本身不泄露秘密，但被拒绝那一轮的中间值（包括触发拒绝的是哪个条件）不能以可观测的方式泄露，否则就绕开了拒绝采样要保护的东西。FIPS 203 和 FIPS 204 把侧信道防护列为实现方的责任，并要求秘密中间值用完即清除；工程上的通行要求是秘密相关的操作全部常量时间，不出现依赖秘密的分支和访存。此外，ML-KEM 的隐式拒绝机制也要求解封装的两条执行路径（校验成功和校验失败）在时间和功耗特征上不可区分。

ML-KEM 和 ML-DSA 的计算热点有两个：NTT 域的多项式运算，以及用 SHAKE 展开矩阵 Â、采样噪声的 Keccak 调用。向量化之后 NTT 变得很便宜，Keccak 往往成为占比更大的部分——Kyber 第三轮曾定义一个用 AES-CTR 和 SHA-2 替代 SHAKE 的「90s」变体，目的就是借用普遍存在的 AES-NI / SHA 硬件指令，这一变体最终没有进入 FIPS 203。NTT 高效实现的关键在于：

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 逆向变换的组合：正向 NTT 的输出按位逆序排列，但 NTT 域内只做逐点运算、不关心顺序，逆变换再恢复自然顺序，所以全程不需要显式的位逆序置换。这也是上面代码中旋转因子要按位逆序存放的原因。

在 x86-64 平台上，AVX2 指令集提供 256 位宽的 SIMD 寄存器，可以同时处理 16 个 16 位整数。ML-KEM 的系数宽度（12 位用于未压缩值，小于 16 位）恰好可以打包到 16 位通道中，Kyber 和 Dilithium 的官方仓库都提供了 AVX2 优化实现。在 ARM 平台上，NEON 指令集提供 128 位宽的 SIMD 寄存器，可同时处理 8 个 16 位整数。

具体的周期数高度依赖 CPU 代际、编译器和实现版本，本文不给自测数字。需要对比时，可以查 SUPERCOP / eBACS 的公开测量，或者在目标机器上用 liboqs 自带的 speed_kem、speed_sig 基准程序实测；公开测量的共同结论是，AVX2 优化后 ML-KEM 的封装、解封装计算量与 X25519 处在同一量级，部署的主要代价在尺寸而不在计算。

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

对于资源受限的嵌入式平台（如 ARM Cortex-M4），内存占用是关键约束，参考实现直接照搬到微控制器上栈开销偏大。优化策略包括：在线生成矩阵 Â 的各行（逐行流式生成，避免同时存储整个矩阵）；将 NTT 变换与采样操作交错进行以复用缓冲区；使用压缩格式存储秘密密钥。pqm4 项目（ARM Cortex-M4 上的后量子密码库）是这一领域的标杆实现。

在进入部署讨论之前，以下速查表汇总了 ML-KEM 三个参数集和 ML-DSA 三个参数集的密钥、密文与签名尺寸（数值取自 FIPS 203 / FIPS 204；私钥按标准的展开格式计，只存 32 字节种子的实现会小得多）：

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

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

与经典方案的尺寸对比

审视这张速查表，一个结论是清晰的：从经典密码到后量子密码，密钥和签名尺寸的膨胀是真实的——ML-KEM-768 的公钥是 X25519 的 37 倍，ML-DSA-65 的签名是 Ed25519 的约 52 倍——但对于绝大多数现代网络应用而言，一个 TLS 握手多传输 1 到 2 KB 的数据是可以承受的。尺寸真正成问题的场景在资源受限的物联网设备上，第九节末尾会具体算一笔账。

下表把 ML-KEM 和 ML-DSA 三个级别的结构参数和传输开销放在一起。ML-KEM 的 core-SVP 列给的是估计范围，随攻击模型和估计器版本浮动几个比特；如上一节所述，它不能与 NIST 级别直接相减得出「安全裕度」。

选型决策框架：对于大多数互联网应用（TLS、SSH、消息协议），ML-KEM-768 + ML-DSA-65（Level 3）是默认选择，尺寸开销适中，也为攻击估计的修订留出了余量。ML-KEM-512 是标准化的 Level 1 参数集，适合尺寸极度受限、保密期较短的场景，但它的安全裕度有过公开争论（见第七节）。ML-KEM-1024 / ML-DSA-87 尺寸约为 Level 3 的 1.3 到 1.4 倍，适合要求 Level 5 的合规场景（例如美国 NSA 的 CNSA 2.0 要求 ML-KEM-1024 与 ML-DSA-87）或需要数十年保密的档案数据。

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

混合 KEM 的主要网络代价是 ClientHello 变大：X25519MLKEM768 的密钥份额为 1216 字节（1184 字节 ML-KEM 公钥加 32 字节 X25519 份额），ClientHello 往往超过一个 TCP 段。计算开销不是瓶颈，真正的问题出在少数对 ClientHello 长度有隐含假设的中间设备上，见本节末尾。

Signal 在 2023 年引入了 PQXDH（Post-Quantum Extended Diffie-Hellman）密钥协商，把 CRYSTALS-Kyber-1024 与 X25519 组合，为首次建立会话的密钥提供后量子保护。Apple 在 2024 年 2 月公布的 iMessage PQ3 协议同样采用 ECDH 与 Kyber 的混合设计，并在会话过程中周期性地做后量子重新协商。云厂商方面，AWS、Google Cloud、Cloudflare 都已在自家 TLS 端点上支持混合后量子密钥交换，具体覆盖范围以各自的官方文档为准。

OpenSSL 3.5（2025 年 4 月）原生加入了 ML-KEM、ML-DSA 和 SLH-DSA，并把 X25519MLKEM768 放进默认的 TLS 组列表；更早的 OpenSSL 3.x 可以通过 Open Quantum Safe（OQS）项目的 oqs-provider 加载 liboqs 中的实现。BoringSSL（Google 维护的 OpenSSL 分支）、AWS-LC（Amazon 维护的密码库）和 wolfSSL 等主流密码库也已原生支持 ML-KEM。

在编程语言层面，Go 1.24 在标准库中加入了 crypto/mlkem，并在 crypto/tls 中默认启用 X25519MLKEM768（Go 1.23 默认启用的是标准化前的 X25519Kyber768Draft00）；Rust 生态有 RustCrypto 的 ml-kem、ml-dsa crate 和 pqcrypto；Java 的 Bouncy Castle 已加入 FIPS 203/204 支持。

本文不给自测的周期数：结果高度依赖 CPU 代际、编译器和实现版本，照抄一组没有环境说明的数字没有意义。需要对比时，查 SUPERCOP / eBACS 的公开测量，或在目标机器上运行 liboqs 的 speed_kem、speed_sig。公开测量反映的量级关系是：ML-KEM 的封装、解封装与 X25519 在同一量级，远快于 RSA-2048 的私钥运算；ML-DSA 的签名因为拒绝采样而耗时波动，验签比签名快得多。部署时的主要代价在尺寸，不在计算。

后量子密码学的工程部署正在以前所未有的速度推进。从浏览器到消息应用，从云服务到嵌入式设备，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 的签名（3309 字节）是 Ed25519（64 字节）的约 52 倍，对于需要频繁验证固件签名的嵌入式设备而言，这不是渐进式的增长，而是质变。后量子迁移的真正挑战不在数据中心，而在网络边缘那些最脆弱、最难升级、部署周期却最长的设备上——这些设备很可能在量子计算机问世时仍在运行今天的经典密码。

从工程实践来看，当前普遍采用的”混合模式”（经典 + 后量子）部署策略，表面上是一种安全的过渡措施，但它实际上暴露了一个深层的认识论困境：我们对任何单一后量子假设都没有足够的信心来独立押注。格基假设虽然已被研究多年（LWE 于 2005 年提出，模格版本 MLWE 的系统研究更晚），但与 RSA 的因子分解假设或椭圆曲线的 ECDLP 假设相比，它的学术审查历史仍然年轻。混合模式的存在本身就是密码学社区对自身知识边界的一种诚实承认——这在密码学史上是罕见的。更实际地说，混合模式还揭示了一个工程权衡：它把 TLS ClientHello 里的密钥份额从 32 字节膨胀到 1216 字节，ClientHello 因此常常跨越多个 TCP 段，一些假设 ClientHello 装得进单个数据包的中间设备（防火墙、负载均衡器）会处理失败、导致握手中断。Chrome 在推广时专门提供了企业策略开关，让受影响的机构先临时关闭后量子密钥交换、再推动设备厂商修复。混合模式不是免费午餐，它是我们为认识论上的审慎所支付的工程代价。

优先读同系列或同问题的下一篇，把单篇消费变成主题集群。

2026-04-13 · cryptography

PQC 算法总览：NIST 标准化竞赛历程与结果、格基/编码基/哈希基等五大技术路线参数对比，以及 ML-KEM、ML-DSA、SLH-DSA 标准选择背后的权衡。

2026-04-04 · cryptography

覆盖对称密码、公钥密码、TLS / PKI、数学基础、格密码与 PQC、国密 SM2/SM3/SM4、零知识证明与同态加密的系统化密码学博客，按工程实践、系统学习、理论研究三条路线组织。

2026-04-04 · cryptography

填充看似简单，却是密码学安全的关键环节——从 PKCS#1 v1.5 的 Bleichenbacher 攻击到 OAEP 的双重哈希防御，本文深入解析填充方案为何如此重要

2026-04-06 · cryptography

格（Lattice）是后量子密码学最重要的数学结构——本文系统讲解格的定义、最短向量问题（SVP）、最近向量问题（CVP）、LLL 算法、LWE/RLWE 假设，为理解后量子密码方案打下基础