ML-KEM (Kyber)
Module-Lattice-Based
Key Encapsulation Mechanism
2024 (FIPS 203)
ML-KEM（Module-Lattice-Based Key Encapsulation Mechanism），原名 Kyber，是由 NIST 于 2024 年发布的后量子密码标准（FIPS 203）。它基于 Module-LWE（模格上的学习误差问题）数学难题，用于密钥封装（Key Encapsulation），旨在替代 RSA 和 ECDH 等经典密钥交换方案，抵抗量子计算机的攻击。
2016 年 NIST 启动后量子密码标准化进程，征集能够抵抗量子计算攻击的公钥密码算法。2017 年收到 82 份提案，经过多轮评估，Kyber 于 2022 年被选为密钥封装的标准算法。2024 年 8 月，NIST 正式发布 FIPS 203，将 Kyber 标准化为 ML-KEM。
Shor 算法能在多项式时间内破解 RSA 和 ECC，这意味着一旦大规模量子计算机出现，当前广泛使用的 TLS 密钥交换将不再安全。ML-KEM 基于的格问题被认为是量子计算无法高效解决的。
ML-KEM 是一种 密钥封装机制（KEM），由三个算法组成：
- KeyGen()：生成公钥/私钥对。公钥可用于封装共享密钥，私钥用于解封装。
- Encaps(pk)：输入公钥，输出共享密钥 K 和密文 ct。
- Decaps(ct, sk)：输入密文和私钥，恢复共享密钥 K。
ML-KEM 的核心构造基于 Module-LWE 问题：给定一个模多项式环上的矩阵 A 和噪声向量 e，区分 (A, A·s + e) 与均匀随机的分布。这个问题的困难性保证了 ML-KEM 的 CPA（选择明文攻击）安全性。通过 Fujisaki-Okamoto 变换，CPA 安全的方案被提升为 CCA（选择密文攻击）安全的 KEM。
| 参数集 | NIST 安全级别 | 公钥大小 | 密文大小 | 私钥大小 | 等效对称安全 |
|---|---|---|---|---|---|
| ML-KEM-512 | Level 1 | 800 B | 768 B | 1,632 B | AES-128 |
| ML-KEM-768 | Level 3 | 1,184 B | 1,088 B | 2,400 B | AES-192 |
| ML-KEM-1024 | Level 5 | 1,568 B | 1,568 B | 3,168 B | AES-256 |
对比传统方案，RSA-2048 公钥约 256 字节但被认为不安全（量子攻击下），而 ECDH P-256 公钥仅 64 字节但同样不抗量子。ML-KEM 在提供后量子安全的同时，密钥和密文尺寸仍然在可接受范围内。
| 方案 | 公钥大小 | 密文/共享密大小 | 抗量子 |
|---|---|---|---|
| RSA-2048 | 256 B | 256 B | 否 |
| ECDH P-256 | 64 B | 64 B | 否 |
| X25519 | 32 B | 32 B | 否 |
| ML-KEM-768 | 1,184 B | 1,088 B | 是 |
| ML-KEM-1024 | 1,568 B | 1,568 B | 是 |
ML-KEM 的安全性基于 Module-LWE 问题的困难性，这是格密码学中最成熟的安全假设之一。NIST 安全级别的含义为：
- Level 1：至少与 AES-128 破解难度相当
- Level 3：至少与 AES-192 破解难度相当
- Level 5：至少与 AES-256 破解难度相当
ML-KEM 采用了严格的安全证明，从 Module-LWE 的困难性到 IND-CCA 安全性之间有可归约证明。此外，ML-KEM 的实现使用了恒定时间算法来抵抗侧信道攻击。
- TLS 1.3：Chrome、Firefox、Cloudflare 等已支持 X25519+ML-KEM-768 混合密钥交换
- 信号协议：Signal 已在后量子密钥协商中集成 Kyber
- Apple：iMessage 于 2023 年引入 PQ3 协议，使用 Kyber 实现后量子安全
- VPN：WireGuard 等正在探索集成 ML-KEM
- S/MIME：RFC 9580 规定在 OpenPGP 中使用 ML-KEM
当前部署普遍采用 混合模式（Hybrid Key Exchange），同时运行经典密钥交换（如 X25519）和 ML-KEM，只有两者同时被攻破时才会失败，确保了前向兼容和过渡期安全。
- 模格密码学数学基础 — 格、多项式环、LWE/SIS 问题的详细数学解释
- NIST (2024). "Module-Lattice-Based Key-Encapsulation Mechanism Standard". FIPS 203.
- Avanzi, R., et al. (2021). "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM". EUROCRYPT 2018, revised.
- Albrecht, M., et al. (2023). "NIST PQC Selection Report". NIST Internal Report.
- Schwabe, P., et al. (2022). "Post-Quantum TLS Without Handshake Signatures". ACM CCS 2022.