【密码学百科】后量子密码总览：NIST 标准化与五大技术路线

一、后量子密码学的背景与紧迫性

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

graph TD
    PQC[后量子密码]
    PQC --> L[格基]
    PQC --> C[编码基]
    PQC --> H[哈希基]
    PQC --> M[多变量]
    PQC --> I[同源基]
    L --> K[ML-KEM]
    L --> D[ML-DSA]
    H --> S[SLH-DSA]

二十世纪末至二十一世纪初，公钥密码学的安全基石——大整数分解问题与离散对数问题——支撑了互联网通信的绝大多数安全协议。RSA、椭圆曲线密码（ECC）以及 Diffie-Hellman 密钥交换等方案，在经典计算模型下被认为是计算上不可行的。然而，1994 年 Peter Shor 提出的量子算法从根本上动摇了这一假设：一台具有足够逻辑量子比特的容错量子计算机（Cryptographically Relevant Quantum Computer, CRQC），能够在多项式时间内分解大整数并求解离散对数，从而彻底瓦解当前主流公钥密码体系的安全性。

量子计算机的工程化进展在近年显著加速。IBM、Google、Quantinuum 等公司持续刷新量子比特数与纠错能力的记录。虽然当前的量子硬件距离破解 RSA-2048 或 ECC-256 仍有相当距离，但密码学界普遍认为”先收集、后解密”（harvest now, decrypt later）的威胁已经真实存在——攻击者今天截获的加密流量，可能在未来十至二十年内被量子计算机解密。对于需要长期保密的数据（如国家机密、医疗档案、金融记录），迁移到抗量子算法的窗口期正在迅速缩小。

美国国家安全局（NSA）于 2022 年发布的 CNSA 2.0（Commercial National Security Algorithm Suite 2.0）指南明确要求：到 2030 年，国家安全系统中的软件与固件必须全面过渡到后量子密码算法；到 2033 年，所有网络设备和操作系统均需完成迁移；到 2035 年，定制化应用和传统系统也必须完成替换。这份时间表向全球传递了一个清晰的信号——后量子迁移不是”是否”的问题，而是”何时完成”的问题。

后量子密码学（Post-Quantum Cryptography, PQC）正是在这一背景下兴起的研究领域。其核心目标是设计在经典计算机上高效运行、同时能够抵抗量子计算机攻击的密码算法。与量子密码（Quantum Cryptography，如量子密钥分发 QKD）不同，后量子密码并不依赖量子力学原理，而是基于被认为对量子计算机仍然困难的数学问题。这意味着后量子密码可以在现有的软硬件基础设施上部署，无需专用的量子信道或量子设备，因而具有更高的实用性和可扩展性。

二、NIST PQC 标准化历程

美国国家标准与技术研究院（NIST）是全球后量子密码标准化进程的核心推动者。早在 2016 年 12 月，NIST 就正式发起了后量子密码标准化竞赛（Post-Quantum Cryptography Standardization Process），向全球密码学研究者征集抗量子密码方案。这一竞赛被广泛类比为当年遴选 AES 的过程，但其复杂程度远超 AES 竞赛——因为 PQC 竞赛同时涵盖密钥封装机制（Key Encapsulation Mechanism, KEM）和数字签名（Digital Signature）两大功能类别，且候选方案来自截然不同的数学基础。

2017 年 11 月，征集期结束，NIST 共收到来自世界各地的 82 份有效提交（另有数份因格式问题被拒绝）。这些方案涵盖了格基（lattice-based）、编码基（code-based）、多变量（multivariate）、哈希基（hash-based）以及同源基（isogeny-based）等多条技术路线。2018 年 4 月，经过初步筛选，69 个方案进入第一轮评估（Round 1）。

第一轮评估持续约一年半。在此期间，全球密码学社区对候选方案进行了密集的密码分析、性能测试和安全性评估。部分方案因遭受有效攻击或存在明显的设计缺陷而被淘汰。2019 年 1 月，NIST 宣布 26 个方案进入第二轮（Round 2）。

第二轮评估进一步聚焦于方案的安全性裕度（security margin）、实现效率和算法灵活性。NIST 特别关注方案在不同硬件平台上的性能表现，包括服务器、桌面、嵌入式设备和智能卡。2020 年 7 月，NIST 从第二轮候选方案中选出 7 个进入第三轮（Round 3）的最终候选方案（finalists），另有 8 个方案列为备选方案（alternate candidates）。

第三轮的 7 个最终候选方案包括：KEM 类别的 CRYSTALS-Kyber、NTRU、SABER 和 Classic McEliece，以及签名类别的 CRYSTALS-Dilithium、FALCON 和 Rainbow。2022 年 7 月，NIST 做出了历史性的决定：选择 CRYSTALS-Kyber 作为 KEM 标准、CRYSTALS-Dilithium 和 FALCON 作为签名标准、SPHINCS+ 作为基于哈希的签名标准。与此同时，Rainbow 因在第三轮末期遭受了 Ward Beullens 的高效密钥恢复攻击而被淘汰。NTRU 和 SABER 虽然未被选中作为首批标准，但其底层的格基数学与 Kyber 密切相关。Classic McEliece 因其密钥尺寸过大被推迟至第四轮继续评估，BIKE 和 HQC 也进入了第四轮的 KEM 备选评估。

NIST 对候选方案的评估标准涵盖多个维度。安全性是首要考量，包括方案的可证明安全归约（provable security reduction）质量、底层困难问题的成熟度以及抵御已知量子和经典攻击的裕度。性能指标包括密钥生成、封装/解封装（或签名/验证）的计算开销，以及公钥、密文和签名的尺寸。此外，NIST 还考虑了算法的实现简洁性、侧信道抵抗能力、知识产权状况以及与现有协议的兼容性。

2024 年 8 月 13 日，NIST 正式发布了首批三项后量子密码标准：FIPS 203（ML-KEM，基于 CRYSTALS-Kyber）、FIPS 204（ML-DSA，基于 CRYSTALS-Dilithium）和 FIPS 205（SLH-DSA，基于 SPHINCS+）。这标志着后量子密码从学术研究正式进入工业部署阶段。

三、NIST 首批标准

NIST 首批发布的三项标准各有侧重，共同构成了后量子密码部署的基本工具箱。

FIPS 203：ML-KEM（Module-Lattice-Based Key-Encapsulation Mechanism） 是基于模格上学习误差问题（Module Learning With Errors, MLWE）的密钥封装机制，其前身为 CRYSTALS-Kyber。ML-KEM 提供三个安全级别的参数集：ML-KEM-512（对应 NIST 安全级别 1，约等效 AES-128）、ML-KEM-768（安全级别 3，约等效 AES-192）和 ML-KEM-1024（安全级别 5，约等效 AES-256）。ML-KEM 的核心优势在于其极为紧凑的密钥和密文尺寸——ML-KEM-768 的公钥仅 1184 字节、密文 1088 字节——以及极快的运算速度。在现代处理器上，ML-KEM 的封装和解封装操作通常只需数十微秒，远快于传统 RSA 和 ECC 方案。ML-KEM 的安全性基于 MLWE 问题的困难性，该问题被认为在量子计算模型下仍然是困难的，且已经过二十余年的密码分析检验。

FIPS 204：ML-DSA（Module-Lattice-Based Digital Signature Algorithm） 是基于模格上 Fiat-Shamir with Aborts 范式的数字签名算法，其前身为 CRYSTALS-Dilithium。ML-DSA 同样提供三个参数集：ML-DSA-44（安全级别 2）、ML-DSA-65（安全级别 3）和 ML-DSA-87（安全级别 5）。ML-DSA 的签名操作基于”拒绝采样”（rejection sampling）技术——签名者反复尝试生成签名，直到输出不泄露私钥信息为止。这种方法的好处是使签名分布独立于私钥，从而实现可证明安全性。ML-DSA-65 的公钥为 1952 字节、签名为 3293 字节，签名和验证速度极快，适合在 TLS 握手、代码签名和证书体系中部署。

FIPS 205：SLH-DSA（Stateless Hash-Based Digital Signature Algorithm） 是基于哈希函数的无状态数字签名算法，其前身为 SPHINCS+。SLH-DSA 的安全性仅依赖于底层哈希函数的安全性，不涉及任何格、编码或数论假设，因此被视为最保守的后量子签名方案。SLH-DSA 提供多组参数，在安全级别、签名尺寸和速度之间进行不同的权衡。例如，SLH-DSA-SHA2-128f（“f”代表快速变体）的签名约 17088 字节，速度较快但签名较大；SLH-DSA-SHA2-128s（“s”代表小签名变体）的签名约 7856 字节，但签名速度较慢。SLH-DSA 的主要优势在于其安全假设极为简单，适合作为”安全后备”（security backstop）部署在对算法多样性有要求的场景中。

四、格基密码路线

格基密码（Lattice-Based Cryptography）是当前后量子密码领域最活跃、应用最广泛的技术路线。其安全性基于格（lattice）中一系列被认为在量子计算模型下仍然困难的计算问题。

格是欧氏空间中由一组基向量的所有整系数线性组合构成的离散点集。在高维空间中，格上的许多计算问题——如最短向量问题（Shortest Vector Problem, SVP）和最近向量问题（Closest Vector Problem, CVP）——被证明是 NP 困难的或在近似意义下是困难的。Shor 算法对这些问题无效，因为格问题不具有周期性结构，无法用量子傅里叶变换加速求解。

学习误差问题（Learning With Errors, LWE）是 Oded Regev 于 2005 年提出的计算困难假设，被证明可以归约到最坏情况下的格困难问题。LWE 的直觉描述是：给定一组带有小噪声的线性方程，恢复未知向量是困难的。形式化地说，给定矩阵 A 和向量 b = As + e（其中 s 是秘密向量、e 是小噪声向量），从 (A, b) 中恢复 s 在计算上是不可行的。LWE 及其结构化变体——环上学习误差（Ring-LWE, RLWE）和模上学习误差（Module-LWE, MLWE）——构成了当前格基密码方案的核心困难假设。RLWE 和 MLWE 通过在多项式环上引入代数结构，在保持安全性的同时显著减小了密钥尺寸和提升了运算效率。

CRYSTALS-Kyber（现标准化为 ML-KEM）是格基 KEM 的代表。Kyber 基于 MLWE 问题构建，采用压缩（compression）技术减小密文尺寸，并通过 Fujisaki-Okamoto 变换将选择明文安全（CPA-secure）的公钥加密方案提升为选择密文安全（CCA-secure）的 KEM。Kyber 在第三轮竞赛中凭借优异的综合性能——紧凑的参数尺寸、极快的运算速度和充分的安全裕度——被选为唯一的 KEM 标准。

以下 Python 代码演示了 ML-KEM 三个安全级别的参数尺寸对比，以及一个基于 LWE 的玩具加密方案，帮助直观理解格基密码的核心原理。

"""
ML-KEM 参数尺寸对比 & LWE 玩具加密演示
注意：玩具示例仅用于阐释原理，不可用于真实场景。
"""
import random

# ========== 第一部分：ML-KEM 参数尺寸对比 ==========
ml_kem_params = {
    "ML-KEM-512  (NIST Level 1)": {"pk": 800,  "sk": 1632, "ct": 768,  "ss": 32},
    "ML-KEM-768  (NIST Level 3)": {"pk": 1184, "sk": 2400, "ct": 1088, "ss": 32},
    "ML-KEM-1024 (NIST Level 5)": {"pk": 1568, "sk": 3168, "ct": 1568, "ss": 32},
}

print("=== ML-KEM (FIPS 203) 参数尺寸对比（字节） ===\n")
print(f"{'方案':<30} {'公钥':>6} {'私钥':>6} {'密文':>6} {'共享密钥':>8}")
print("-" * 62)
for name, sizes in ml_kem_params.items():
    print(f"{name:<30} {sizes['pk']:>6} {sizes['sk']:>6} "
          f"{sizes['ct']:>6} {sizes['ss']:>8}")

# 与经典方案对比
print("\n--- 与经典 ECDH (P-256) 对比 ---")
print(f"{'ECDH P-256':<30} {'32':>6} {'32':>6} {'32':>6} {'32':>8}")
print("\n可以看到 ML-KEM 的密钥和密文尺寸比经典方案大一个数量级，")
print("但在后量子 KEM 中已属非常紧凑。\n")

# ========== 第二部分：LWE 玩具加密 ==========
# 参数（极小，仅演示用；真实 ML-KEM 使用 n=256, q=3329 等）
n = 4       # 向量维度
q = 251     # 模数（素数，需足够大以容纳噪声）

def vec_add(a, b):
    return [(x + y) % q for x, y in zip(a, b)]

def vec_dot(a, b):
    return sum(x * y for x, y in zip(a, b)) % q

def mat_vec_mul(A, v):
    return [vec_dot(row, v) for row in A]

def small_error():
    """生成小噪声（模拟离散高斯分布）"""
    return random.choice([-1, 0, 1])

def keygen():
    """密钥生成：公钥 (A, b = A*s + e)，私钥 s"""
    A = [[random.randint(0, q - 1) for _ in range(n)] for _ in range(n)]
    s = [small_error() for _ in range(n)]  # 小秘密（与 ML-KEM 一致）
    e = [small_error() for _ in range(n)]
    b = vec_add(mat_vec_mul(A, s), e)
    return (A, b), s

def encrypt(pk, bit):
    """加密单个比特 (0 或 1)"""
    A, b = pk
    r = [random.choice([0, 1]) for _ in range(n)]
    # u = A^T * r + e1,  v = b · r + e2 + bit * ⌊q/2⌋
    AT = [[A[j][i] for j in range(n)] for i in range(n)]
    e1 = [small_error() for _ in range(n)]
    u = vec_add(mat_vec_mul(AT, r), e1)
    e2 = small_error()
    v = (vec_dot(b, r) + e2 + bit * (q // 2)) % q
    return u, v

def decrypt(sk, ct):
    """解密：计算 v - s · u，判断更接近 0 还是 ⌊q/2⌋"""
    u, v = ct
    inner = vec_dot(sk, u)
    plain = (v - inner) % q
    return 0 if plain < q // 4 or plain > 3 * q // 4 else 1

print("=== LWE 玩具加密演示 (n={}, q={}) ===\n".format(n, q))
pk, sk = keygen()
print(f"公钥矩阵 A（{n}×{n}）和向量 b 已生成")
print(f"私钥 s = {sk}\n")

success = 0
trials = 20
for i in range(trials):
    bit = random.randint(0, 1)
    ct = encrypt(pk, bit)
    dec = decrypt(sk, ct)
    ok = "✓" if dec == bit else "✗"
    if dec == bit:
        success += 1
    if i < 5:
        print(f"  明文={bit}, 解密={dec}  {ok}")
print(f"  ... 共 {trials} 次试验")
print(f"\n解密正确率：{success}/{trials} = {success/trials:.0%}")
print("（噪声参数合理时正确率应接近 100%）")

CRYSTALS-Dilithium（现标准化为 ML-DSA）是格基签名的代表。Dilithium 基于 MLWE 和模上短整数解问题（Module-SIS），采用 Fiat-Shamir with Aborts 范式构建。签名过程中，签名者生成随机掩蔽向量、计算承诺、利用哈希函数生成挑战，然后检查响应是否会泄露私钥信息。若泄露风险超过阈值则拒绝（abort）并重新采样。这种拒绝采样策略确保了签名分布与私钥的统计独立性。

NTRU 家族是格基密码中历史最悠久的分支。NTRU 加密方案早在 1996 年就由 Jeffrey Hoffstein、Jill Pipher 和 Joseph Silverman 提出，远早于 LWE 的形式化。NTRU 基于截断多项式环上的困难问题，其安全性与格中的近似 SVP 相关。虽然在第三轮竞赛中 NTRU（以 NTRU-HPS 和 NTRU-HRSS 两种变体参赛）未被选为首批标准，但其在嵌入式系统中的高效实现和长期的安全分析历史使其在特定场景中仍具有吸引力。FALCON 签名方案也属于 NTRU 家族——它基于 NTRU 格上的 GPV 框架（Gentry-Peikert-Vaikuntanathan）和快速傅里叶采样，生成极为紧凑的签名（FALCON-512 的签名仅约 666 字节），但其实现复杂度较高，对浮点精度和侧信道防护提出了更严格的要求。NIST 计划将 FALCON 作为 FIPS 206 发布。

五、编码基密码路线

编码基密码（Code-Based Cryptography）的历史可以追溯到 1978 年 Robert McEliece 提出的 McEliece 密码系统——这是最早的公钥加密方案之一，甚至早于 RSA 的广泛部署。McEliece 的核心思想是将纠错码的解码问题作为陷门：拥有私钥的人知道码的结构，可以高效解码；而攻击者面对的是一个看似随机的线性码，对其解码等价于求解 NP 困难的一般线性码译码问题。

McEliece 方案的安全性经受住了四十多年的密码分析检验，且 Shor 算法对一般线性码译码问题无效。然而，McEliece 的致命弱点在于其巨大的公钥尺寸。经典 McEliece（Classic McEliece）使用二元 Goppa 码作为底层纠错码，在 NIST 安全级别 1 下的公钥约为 261 千字节（KB），在安全级别 5 下甚至接近 1 兆字节（MB）。这使得 McEliece 在带宽受限的场景（如 TLS 握手）中难以直接部署。

Niederreiter 方案是 McEliece 的对偶形式，使用校验矩阵替代生成矩阵进行加密。两者在安全性上被证明是等价的，但 Niederreiter 的密文更为紧凑。许多现代编码基方案实际上采用了 Niederreiter 范式或其变体。

Classic McEliece 在 NIST 竞赛中一路进入第四轮。尽管其公钥尺寸限制了应用场景，但其安全性的保守程度几乎无可匹敌——底层的二元 Goppa 码译码问题经过数十年的分析仍未出现显著的算法改进。NIST 将其视为一种”保险”方案，适用于密钥可以预先分发或存储空间充裕的场景。

BIKE（Bit Flipping Key Encapsulation）和 HQC（Hamming Quasi-Cyclic）是第四轮中基于结构化码的两个 KEM 候选方案。与 Classic McEliece 不同，BIKE 和 HQC 使用准循环（quasi-cyclic）码结构来大幅压缩公钥尺寸。BIKE 基于准循环中密度奇偶校验码（QC-MDPC），利用比特翻转译码算法进行解封装；HQC 基于准循环码的随机化编码方法。两者的公钥和密文尺寸在数千字节级别，远优于 Classic McEliece，但仍大于格基方案。BIKE 和 HQC 的主要挑战在于解封装失败率（decapsulation failure rate）的精确分析——即使极低的失败概率也可能被利用构造选择密文攻击。

编码基路线的另一重要分支是基于秩度量码（rank-metric code）的方案，如 ROLLO 和 RQC。秩度量码将向量空间的秩距离替代汉明距离，提供了一种不同的困难问题来源，但目前这些方案的安全性分析尚不够成熟，未进入 NIST 竞赛的后续轮次。

六、哈希基签名路线

哈希基签名（Hash-Based Signatures）是后量子签名方案中安全假设最简单、理论基础最坚实的一类。其安全性仅依赖于底层哈希函数的抗原像性（preimage resistance）和抗碰撞性（collision resistance），不涉及任何数论或代数结构假设。

哈希基签名的起源可以追溯到 1979 年 Leslie Lamport 提出的一次性签名方案（Lamport One-Time Signature, OTS）。Lamport 方案的思想极为简洁：为消息的每一比特准备两个随机值并公开其哈希值作为公钥；签名时根据消息比特选择性地揭示对应的原像。由于哈希函数的单向性，攻击者无法伪造签名。Lamport 方案的缺点是公钥和签名尺寸过大，且每个密钥对只能安全地签名一条消息。

Ralph Merkle 于 1979 年提出了 Merkle 签名方案（Merkle Signature Scheme, MSS），利用 Merkle 哈希树将多个一次性签名密钥组织在一起，使一个根公钥可以验证多个签名。哈希树的每个叶子节点对应一个 OTS 密钥对的公钥哈希，签名时附带从叶子到根的认证路径（authentication path）。MSS 是有状态的（stateful）——签名者必须维护一个计数器以确保每个 OTS 密钥只使用一次。若同一 OTS 密钥被重复使用，安全性将被完全破坏。

XMSS（eXtended Merkle Signature Scheme）和 LMS（Leighton-Micali Signature Scheme）是两种已标准化的有状态哈希基签名方案。XMSS 由 IETF 在 RFC 8391 中标准化，LMS 由 NIST 在 SP 800-208 中推荐。两者都基于 Merkle 树结构，并引入了改进的 OTS 构造（XMSS 使用 WOTS+，LMS 使用 LM-OTS）以优化签名尺寸。有状态方案的签名紧凑且速度快，但状态管理的严格要求限制了其适用范围——在分布式系统或高并发场景中，确保 OTS 密钥不被重复使用是一项重大的工程挑战。

SPHINCS+（现标准化为 SLH-DSA/FIPS 205）是哈希基签名路线中最重要的突破——它是一种无状态（stateless）方案。SPHINCS+ 通过构建一个超级树（hypertree）结构来消除对状态的依赖：整个签名密钥空间被组织为多层 Merkle 树的嵌套结构，签名时通过消息哈希确定性地选择使用哪个叶子节点。由于签名过程是确定性的（或使用消息相关的随机化），相同的消息总是产生相同的签名，从而避免了 OTS 密钥重复使用的风险。SPHINCS+ 内部使用了三种子组件：WOTS+（Winternitz OTS）作为一次性签名、XMSS 树作为少次签名，以及 FORS（Forest of Random Subsets）作为少次签名的前端。

无状态哈希基签名的代价是签名尺寸和签名速度。SLH-DSA 的签名在 7856 到 49856 字节之间，远大于格基方案的签名。签名速度也显著慢于 ML-DSA——SLH-DSA-SHA2-128s 的签名操作可能需要数十毫秒，而 ML-DSA-65 通常在微秒级别完成。然而，SLH-DSA 的验证速度相对较快，且其安全性假设的简洁性使其成为后量子签名部署中不可或缺的”保底”选项。

有状态与无状态方案的选择取决于具体部署场景。对于能够可靠管理状态的系统（如固件签名服务器、证书颁发机构内部签名），有状态方案（XMSS/LMS）提供更紧凑的签名和更高的效率。对于无法保证状态安全性的通用场景（如 TLS 认证、代码签名），无状态方案（SLH-DSA）是更安全的选择。

七、多变量密码路线

多变量密码（Multivariate Cryptography）基于多变量二次方程组求解问题（Multivariate Quadratic Problem, MQ 问题）的困难性。给定一组在有限域上的多元二次多项式方程，求解一组满足所有方程的未知数被证明是 NP 困难的，且目前没有已知的量子算法能显著加速这一问题的求解。

多变量密码方案的一般构造遵循”中心映射加扰动”范式：选择一个具有特殊结构（从而可以高效求逆）的中心映射 F，然后通过两个秘密的可逆仿射变换 S 和 T 对其进行混淆，得到公钥 P = S ∘ F ∘ T。签名验证只需要计算多项式映射（矩阵乘法和域运算），速度极快；签名生成则需要知道 S、T 和 F 的结构以逆向求解。

Oil-Vinegar（油醋）方案是多变量签名中最经典的构造之一。其中心映射将变量分为”油变量”（oil）和”醋变量”（vinegar），利用两类变量之间的特殊二次结构实现高效求逆。Unbalanced Oil-Vinegar（UOV）方案通过增大醋变量与油变量的比例来增强安全性，是多变量签名中历史最悠久且仍被认为安全的构造之一。

Rainbow 是由 Jintai Ding 和 Dieter Schmidt 于 2005 年提出的多层 Oil-Vinegar 方案，通过引入多层结构在保持安全性的同时减小签名和公钥尺寸。Rainbow 在 NIST 竞赛中一路进入第三轮最终候选方案，被认为是多变量路线最有竞争力的代表。然而，2022 年 2 月，Ward Beullens 发表了一种针对 Rainbow 的高效密钥恢复攻击——利用 Rainbow 多层结构中的矩形 MinRank 问题的代数性质，攻击者仅需一台普通笔记本电脑和一个周末的时间就能恢复 Rainbow 的私钥。这一毁灭性攻击导致 Rainbow 被 NIST 淘汰，也给整个多变量路线带来了重大打击。

Rainbow 失败的技术剖析与多变量路线的教训

Rainbow 的陨落值得深入剖析，因为它揭示了后量子密码方案评估中一个反复出现的风险模式：结构化陷门在提供效率的同时暴露了攻击面。

Beullens 的攻击分为两个独立的路径，任一路径都足以恢复私钥：

1. 矩形 MinRank 攻击。 Rainbow 的多层结构意味着其公钥的二次形式矩阵具有特殊的秩结构——在特定的变量赋值下，某些矩阵的秩会显著降低。Beullens 利用这一结构性弱点，将密钥恢复归约为一个矩形 MinRank 问题，并用 Kipnis-Shamir 方法的改进变体在 2^{52} 次操作内求解——对于标称 128 位安全性的参数集（Rainbow Level I），这意味着安全性实际仅为约 52 位。

2. 交叉求解攻击（intersection attack）。 利用 Rainbow 两层结构中”油空间”的交集性质，通过求解一个过定的二次方程组来直接恢复油空间。

攻击的时间线令人警醒：Rainbow 在 NIST 竞赛中经历了近五年的公开分析（2017-2022），参加了密码学界最密集的审查——但致命攻击直到标准化决定即将公布时才出现。这为后量子密码方案的安全性评估提供了一个重要教训：竞赛期间无人攻破不等于方案安全，尤其对于安全性分析不够成熟的数学假设。

与 Rainbow 的遭遇形成对比的是，ML-KEM 和 ML-DSA 所依赖的 LWE/MLWE 假设已经过二十余年的系统性密码分析，且 LWE 到最坏情况格困难问题的归约提供了额外的理论保障。这种安全性分析深度上的差距，是 NIST 偏好格基方案的深层原因之一。

GeMSS（Great Multivariate Short Signature）是另一种进入 NIST 竞赛第二轮的多变量方案，基于 HFE（Hidden Field Equations）变体构建。GeMSS 的签名极为紧凑（仅数十字节），但公钥尺寸巨大（数百千字节至兆字节级别），签名速度也较慢，最终未能进入第三轮。

Rainbow 被攻破后，多变量路线的当前研究重新聚焦于 UOV 及其改进方案。NIST 在 2023 年发起了新一轮签名方案征集（Additional Digital Signature Schemes），UOV 的多个变体（如 MAYO、QR-UOV、TUOV、VOX 等）参与了提交。这些方案通过不同的参数优化和结构改进试图在安全性和效率之间取得更好的平衡，但多变量路线整体上仍面临公钥尺寸过大、安全性分析不够稳固等挑战。

八、同源密码路线

同源密码（Isogeny-Based Cryptography）是后量子密码五大路线中最年轻、也最戏剧性的一条。其安全性基于椭圆曲线之间的同源映射（isogeny）计算问题——给定两条同源的椭圆曲线，求连接它们的同源映射在计算上是困难的。

SIDH（Supersingular Isogeny Diffie-Hellman）由 Luca De Feo 和 David Jao 于 2011 年提出，是第一个实用化的同源密钥交换协议。SIDH 的最大优势在于其极为紧凑的公钥和密文——在所有后量子 KEM 中，SIDH/SIKE 的通信开销最小，公钥和密文各仅数百字节。SIKE（Supersingular Isogeny Key Encapsulation）是 SIDH 的 KEM 封装版本，参与了 NIST 竞赛并一路进入第四轮候选方案。

然而，2022 年 7 月，比利时鲁汶大学的 Wouter Castryck 和 Thomas Decru 发表了一篇震撼密码学界的论文，提出了对 SIDH/SIKE 的高效多项式时间攻击。Castryck-Decru 攻击利用了 SIDH 协议中公开的扭转点信息（torsion point information），结合高维阿贝尔簇的同源理论，能够在普通个人电脑上数分钟内完全恢复 SIKE 的私钥。这一攻击在密码学历史上几乎史无前例——一个已进入标准化最终阶段的候选方案被彻底攻破，且攻击方法优雅而出人意料。随后，Maino 和 Martindale、Robert 等研究者分别独立提出了类似的攻击路径，进一步巩固了 SIDH/SIKE 不安全的结论。

需要特别强调的是，Castryck-Decru 攻击的关键在于 SIDH 协议中公开的辅助扭转点信息，而非同源计算本身。如果不公开这些扭转点，一般的超奇异同源问题仍被认为是困难的。这一认识引导了同源密码后续研究的方向。

CSIDH（Commutative Supersingular Isogeny Diffie-Hellman）是另一种基于同源的密钥交换协议，使用交换群作用（commutative group action）框架，避免了公开扭转点信息。因此，CSIDH 不受 Castryck-Decru 攻击影响。然而，CSIDH 面临量子亚指数攻击（基于 Kuperberg 算法的变体）的威胁，其具体安全参数的确定仍存在争议。此外，CSIDH 的运算速度远慢于格基方案，限制了其实际部署。

SQIsign（Short Quaternion and Isogeny Signature）是同源路线中最受关注的签名方案。SQIsign 基于四元数代数（quaternion algebra）与同源映射之间的 Deuring 对应（Deuring correspondence），提供极为紧凑的签名（在 NIST 安全级别 1 下仅约 177 字节）和公钥（64 字节），是所有后量子签名方案中通信开销最小的。SQIsign 已提交至 NIST 的额外签名方案征集，其参数尺寸上的优势使其备受关注。然而，SQIsign 的签名速度较慢（约需数百毫秒至数秒），且其安全性依赖于超奇异同源问题和 Deuring 对应的计算困难性假设，这些假设的分析深度尚不及 LWE 等成熟假设。

同源密码路线在经历了 SIDH/SIKE 的挫折后，研究重心已转向不公开扭转点信息的协议设计（如基于群作用的框架）以及基于高维同源的新构造。尽管当前同源方案在性能上难以与格基方案竞争，其独特的代数结构和极紧凑的参数尺寸使其在理论研究和特定应用场景中仍具有重要价值。

同源路线的困境与前景评估

SIKE 的崩溃和 Rainbow 的失败有着惊人的相似之处——两者都因为公开了过多的代数结构信息而被攻破。但两者的深层原因不同：Rainbow 的问题在于多层结构引入的秩缺陷，而 SIKE 的问题在于公开的扭转点基暴露了同源映射的内部结构。

同源路线当前面临的核心挑战可以从三个维度理解：

安全假设的成熟度。 与 LWE（2005 年提出，2009 年 Regev 获得哥德尔奖）相比，超奇异同源问题的系统性分析历史要短得多。CSIDH 依赖的群作用同源问题（Group Action Inverse Problem, GAIP）虽然避免了 SIKE 的扭转点暴露，但面临 Kuperberg 类量子亚指数攻击的威胁。当前 CSIDH 的安全参数选取存在争议——不同的攻击成本模型给出的安全性估计可能相差 50 位以上。

性能瓶颈。 同源计算本质上是逐步遍历同源图（isogeny graph）中的路径，每一步涉及椭圆曲线上的点运算。CSIDH-512 的密钥交换约需 40 毫秒（对比 ML-KEM 的微秒级），且优化空间有限——加速同源计算需要更好的椭圆曲线算术，而非更好的算法结构。SQIsign 的签名更慢（数百毫秒到数秒），尽管其参数尺寸极为诱人（签名仅 177 字节，公钥 64 字节）。

缺乏成熟的可证明安全框架。 格基方案拥有从 LWE 到最坏情况 GapSVP 的归约链，提供了清晰的安全性论证。同源方案目前缺乏类似的系统性归约——多数安全性论证依赖于”最优已知攻击”的启发式分析，而非形式化的困难问题归约。

九、四类技术路线核心参数对比

下表在统一安全级别（NIST Level 3 或等效参数）下，对格基、编码基、哈希基、多变量四类路线的代表方案进行定量对比。速度数据取自 Intel x86-64（含 AVX2）平台上的参考实现基准测试，仅供量级参考。

KEM 方案（NIST Level 3 等效）：

签名方案（NIST Level 2-3 等效）：

从表中可以提炼出三个结构性判断：

1. 格基方案在综合效率上一骑绝尘。 ML-KEM-768 的公钥+密文总开销仅 2,272 字节，全部操作在微秒级完成。HQC-192 总开销 13,548 字节，Classic McEliece 公钥超过 500 KB。

2. “最坏情况到平均情况归约”是格基方案的理论护城河。 Regev 在 2005 年证明，若能高效求解随机 LWE 实例，则能求解所有格上的 GapSVP 实例——LWE 不存在”碰巧容易的随机实例”。编码基和多变量方案缺乏这类归约，其安全性依赖于”随机实例经验上是困难的”这一更弱的信念。

3. 哈希基方案是唯一”假设归零”的路线。 SLH-DSA 的安全性仅依赖哈希函数的基本性质，不涉及任何代数结构假设。代价是签名尺寸比 ML-DSA 大一个数量级，签名速度慢三个数量级。

十、淘汰方案深度剖析

NIST 竞赛不仅选出了赢家，也淘汰了三个值得深入分析的方案——Rainbow、SIKE 和 SABER。三者的出局原因截然不同，但共同构成了理解 NIST 选择逻辑的必要背景。

Rainbow：矩形 MinRank 攻击的暴死

Rainbow 在竞赛中走完了五年的全部审查周期，进入最终候选名单——然后在标准宣布前夕被一纸论文击杀。

2022 年 2 月，Ward Beullens 发表论文 Breaking Rainbow Takes a Weekend on a Laptop，利用 Rainbow 多层 Oil-Vinegar 结构中隐含的秩缺陷，将密钥恢复归约为矩形 MinRank 问题。Rainbow 的公钥映射在特定变量赋值下，其雅可比矩阵的秩会系统性地降低；Beullens 利用 Kipnis-Shamir 方法的改进变体，在极低复杂度内求解了这一结构性弱点。

Rainbow 之死的核心教训：多层陷门结构在提供效率增益的同时，引入了可被代数方法利用的秩缺陷。单层 UOV 没有这个问题，多变量路线因此回归 UOV 及其变体（MAYO、QR-UOV 等），但整条路线在 NIST 标准化主赛道上已退至边缘。

SIKE/SIDH：同源路线的崩塌

Rainbow 被击杀仅五个月后，SIKE 遭遇了更为戏剧性的终结。Wouter Castryck 和 Thomas Decru 发现，SIDH 协议中公开的扭转点像（torsion point images）构成致命的信息泄露。攻击利用 Kani 定理将同源恢复问题转化为高维阿贝尔簇上的可解问题——SIKE-p434（Level 1）在普通 PC 上约 4 分钟内被完全攻破。攻击是多项式时间的，无法通过增大参数修补。

SIKE 之死与 Rainbow 之死有一个深层共性：两者都因为公开了过多的代数结构信息而暴露攻击面。Rainbow 公开的公钥暴露了多层结构的秩缺陷；SIDH 公开的扭转点像暴露了同源映射的内核结构。

Castryck-Decru 攻击不否定超奇异同源问题本身的困难性，但同源路线整体已从 NIST 标准化主赛道掉队：CSIDH 面临 Kuperberg 类量子亚指数攻击的参数争议（不同攻击成本模型给出的安全性估计可能相差 50 位以上），SQIsign 速度过慢且安全假设不够成熟——同源路线短期内难以产出可部署的标准方案。

SABER：性能优秀却落选

SABER 没有被攻破，Level 3 参数（公钥 992 字节、密文 1,088 字节）甚至略优于 ML-KEM-768，但最终仍然落选。SABER 基于模上学习舍入问题（Module Learning With Rounding, MLWR），将 MLWE 中的”加噪声”替换为”舍入”操作，消除了显式噪声采样步骤。

NIST 选择 Kyber 而非 SABER 的关键考量：

1. 归约链长度。 MLWE 到 GapSVP 的归约直接且成熟。MLWR 需额外经过 MLWE（MLWR → MLWE → GapSVP），归约损失更大。

2. 密码分析密度。 截至 2022 年，针对 MLWE/LWE 的密码分析论文数量远多于 MLWR，MLWE 经受了更密集的学术检验。

3. NTT 友好性。 Kyber 使用 NTT 友好的模数 q = 3329 和多项式环 Z_q[x]/(x^256+1)，各平台的 NTT 加速实现高度统一。SABER 使用 2 的幂模数，虽简化了舍入操作，但 NTT 加速不如 Kyber 灵活。

4. 生态统一。 当两个方案基于高度相似的假设且性能差距微小时，NIST 倾向于只标准化一个以避免生态碎片化。

十一、NIST 标准选择背后的现实权衡

Kyber 胜出 NTRU：归约质量与实现一致性

NTRU 拥有近三十年的密码分析历史（1996 年提出），封装/解封装速度甚至快于 Kyber——核心运算是多项式乘法而非矩阵-向量乘法。NIST 仍选择 Kyber 的理由体现了对”可证明安全”框架的重视：

• 归约质量。 Kyber 基于 MLWE，拥有经由 Regev-Peikert-Micciancio 归约链到最坏情况 GapSVP 的严格归约。NTRU 的安全假设——“NTRU 格上的近似 SVP 是困难的”——被广泛接受，但缺乏同等质量的最坏情况归约。NIST 在报告中表示 Kyber 的安全性论证”更加干净和可理解”。

• 跨安全级别的代码复用。 Kyber 的模格结构通过增大矩阵维度（2 → 3 → 4）提升安全性，各级别共享大部分代码路径，降低实现与审计成本。NTRU 不同参数集涉及不同的多项式度数和模数选择，代码路径差异更大。

• 解封装失败率。 Kyber 经 FO 变换后解封装失败概率严格为零（通过参数选择保证）。NTRU-HPS 存在微小但非零的解封装失败率，需额外处理逻辑。

Dilithium 优于 Falcon：恒定时间实现的工程代价

FN-DSA（FALCON）的签名仅 666 字节（Level 1），不到 ML-DSA-44 的 2,420 字节的三分之一。但 NIST 将 ML-DSA 列为首选、FALCON 作为补充的决定，揭示了工程可实现性在标准化中的隐性权重。

FALCON 的核心挑战在于签名过程中的离散高斯采样（discrete Gaussian sampling over NTRU lattices）。该步骤依赖双精度浮点运算——在缺乏硬件浮点单元的嵌入式平台上速度骤降一到两个数量级。更关键的是，浮点运算的执行时间依赖操作数值（如非规格化数处理），使恒定时间实现（防止计时侧信道攻击）极为困难。反观 ML-DSA 的全部核心运算——多项式乘法、NTT、拒绝采样——都是整数运算，恒定时间实现直截了当。

NIST 的判断：ML-DSA 的签名尺寸虽大但在现代网络中完全可接受（3,293 字节对 TLS 握手的影响微乎其微），而 FALCON 的实现复杂度可能导致部分实现出现侧信道漏洞，得不偿失。FALCON 被保留为 FIPS 206 标准，供签名尺寸有极端需求的场景（如证书链嵌入受限环境）使用。

SPHINCS+ 作为后备：假设多样性的风险对冲

SLH-DSA 的签名比 ML-DSA 大 5 到 15 倍，签名速度慢三个数量级。NIST 选择它的理由不是性能，而是一个更根本的考量：如果 LWE 假设在未来被攻破怎么办？

2022 年 Rainbow 和 SIKE 的相继崩塌证明，经过五年公开审查的方案仍可能在一夜之间被攻破。将全部签名标准建立在格假设上是不可接受的集中风险。SLH-DSA 的安全性仅依赖 SHA-256 或 SHAKE256 的标准性质——二次前像抗性、伪随机性——与任何代数结构完全无关。即使出现攻破 LWE 的突破性算法，SLH-DSA 仍然安全。

SLH-DSA 在标准体系中的角色因此是明确的：它不是日常签名的首选方案，而是对冲格假设风险的安全保险——在需要假设多样性的场景（政府系统、关键基础设施）中作为必选项部署。

十二、后量子迁移策略

后量子密码的标准化只是万里长征的第一步。将整个互联网基础设施、企业系统和嵌入式设备从经典密码迁移到后量子密码，是一项规模空前的工程挑战。

混合模式（Hybrid Mode） 是当前最受推荐的迁移策略。混合模式同时使用一个经典算法（如 ECDH）和一个后量子算法（如 ML-KEM）进行密钥协商，将两者派生的密钥材料组合后用于会话加密。只要两个算法中有一个是安全的，混合方案就是安全的——这意味着即使后量子算法在未来被发现存在缺陷，系统仍然受到经典算法的保护；反之，如果量子计算机提前到来，后量子算法也能提供防护。Google 早在 2016 年就在 Chrome 中实验了 ECDH + New Hope（一种格基方案）的混合密钥交换，Cloudflare 和 Amazon Web Services 也在 2023 年开始大规模部署基于 X25519 + ML-KEM-768 的混合 TLS。IETF 已制定了多项关于混合密钥交换和混合签名的草案标准。

算法选择指南 方面，不同的应用场景对后量子算法有不同的需求。对于密钥交换和封装，ML-KEM 是首选方案，其性能和参数尺寸在绝大多数场景中都是最优的。对于数字签名，需要根据具体需求在 ML-DSA、SLH-DSA 和未来的 FALCON（FIPS 206）之间进行选择：ML-DSA 提供最佳的综合性能；SLH-DSA 提供最保守的安全假设；FALCON 提供最紧凑的签名尺寸但实现复杂。

工业部署现状 方面，后量子密码的实际部署正在迅速推进。在 TLS 协议层面，Google Chrome、Mozilla Firefox 和 Apple Safari 等主流浏览器已支持或正在测试 ML-KEM 混合密钥交换。Cloudflare 报告其全球流量中已有相当比例使用了后量子密钥交换。在消息传递领域，Signal 协议于 2023 年引入了基于 ML-KEM 的 PQXDH（Post-Quantum Extended Diffie-Hellman）协议，Apple 的 iMessage 也部署了类似的后量子保护。在证书体系方面，多家证书颁发机构（CA）正在实验支持后量子签名的 X.509 证书，但完整迁移仍面临证书链膨胀和兼容性等挑战。

在操作系统和密码库层面，OpenSSL 3.x 通过 OQS（Open Quantum Safe）项目的 provider 支持了所有 NIST 标准化的后量子算法。BoringSSL（Google 维护的 OpenSSL 分支）已在生产环境中启用了 ML-KEM 支持。微软的 SymCrypt 和 AWS 的 s2n-tls 也相继集成了后量子算法。在硬件层面，多家芯片厂商正在研究在安全芯片（如 TPM、安全元件）中实现后量子算法的硬件加速。

值得注意的是，后量子迁移并非一次性的”交换”事件，而是一个渐进的、持续数年的过程。迁移的第一步通常是在密钥交换中部署混合方案以保护前向安全性（因为”先收集、后解密”威胁主要针对加密数据）。签名的迁移可以稍后进行，因为签名的安全性主要在验证时刻有效即可。然而，对于长寿命的签名场景（如代码签名、证书签名），尽早迁移同样至关重要。

后量子密码学正处于从标准化到大规模部署的关键转折期。NIST 的首批标准为全球提供了明确的算法选择依据，而混合模式则为平稳过渡提供了工程上的安全网。五大技术路线各有千秋——格基方案以其卓越的综合性能成为主力军，编码基和哈希基方案以其成熟的安全性分析提供了必要的多样性，多变量和同源路线则在参数效率和理论深度方面持续贡献新的思想。面对量子计算时代的到来，密码学社区的共识已经清晰：迁移必须从现在开始。

十三、面向工程团队的后量子迁移决策树

对于正在评估后量子迁移时机和策略的工程团队，以下决策树提供了一条结构化的决策路径。

[你的系统是否处理需要长期保密的数据？]
 │
 ├── 是（医疗记录、政府机密、金融档案、知识产权等保密期 > 10 年）
 │    │
 │    └──→ 立即部署混合方案（经典 + 后量子）
 │         │
 │         ├── 密钥交换：优先部署 ML-KEM + ECDH 混合模式
 │         │   （防御"先收集、后解密"威胁）
 │         │
 │         ├── 签名：评估 ML-DSA 混合签名
 │         │   （长寿命签名场景如代码签名、证书签名需优先迁移）
 │         │
 │         └── 对称密码：确认使用 AES-256（无需紧急变更）
 │
 └── 否（数据保密期 < 10 年，或主要关注完整性/认证）
      │
      ├── [你的系统是否需要密码敏捷性？]
      │    │
      │    ├── 否 → 现在就开始重构以支持算法可替换
      │    │        （这是迁移的最大工程瓶颈）
      │    │
      │    └── 是 → 进入监控与规划阶段
      │
      └──→ 监控与规划（2025-2030）
           │
           ├── 跟踪 NIST 标准最终版本和行业最佳实践
           ├── 在非生产环境中测试 ML-KEM / ML-DSA 集成
           ├── 评估密码库（OpenSSL 3.x / BoringSSL）的 PQC 支持成熟度
           └── 制定分阶段迁移计划：密钥交换优先 → 签名次之 → 全面替换

笔者认为，“先收集、后解密”（Harvest Now, Decrypt Later）是推动立即采纳后量子密码最有说服力的论据，即使在标准尚未完全尘埃落定的今天也是如此。其逻辑极为简明：如果对手现在截获了你的加密通信，并将密文存储起来等待量子计算机成熟后解密，那么你的数据保密期限就不取决于”量子计算机什么时候出现”，而取决于”你的数据需要保密多久”。对于医疗记录（保密期可达 50 年以上）、国家安全情报、长期商业秘密等场景，威胁窗口已经打开。从工程实践来看，混合方案是一种近乎零风险的过渡策略——即使后量子算法日后被发现存在弱点，经典算法层仍提供保护；反之亦然。等待”完美标准”出台再行动的组织，可能正在以数据安全为代价换取工程便利。密码学史反复证明：迁移所需的时间总是超出预期，而威胁到来的速度总是快于预期。

一个经常被忽视的观点是，NIST 后量子竞赛揭示了密码学标准化中一个出人意料的事实：最终胜出的算法未必是数学上最优雅的，而是工程上最”无聊”的。ML-KEM（Kyber）在决赛圈中胜出，部分原因在于它的参考实现是所有候选方案中最简单、最易审计、边界情况最少的。它的模格结构足够标准化，不需要特殊的采样技巧或复杂的错误纠正机制；它的解封装流程通过 FO 变换实现了干净的”解密-重加密-比对”逻辑，几乎没有给实现者留下犯错的空间。这与 AES 在 2000 年竞赛中的胜出有着惊人的相似：Rijndael 不是当时安全余量最大的候选方案（Serpent 更保守），也不是最快的（Twofish 在某些平台上更快），但它在所有维度上都”足够好”，且实现起来最为直截了当。对密码学标准化而言，这里有一条永恒的教训——在安全性相当的候选方案之间，保守的工程选择几乎总是胜过激进的数学创新。

密码学百科系列 · 第 57 篇

← 上一篇：Shor 算法与 Grover 算法 | 系列目录 | 下一篇：格基后量子方案 →