【密码学百科】格基后量子方案：ML-KEM（Kyber）与 ML-DSA（Dilithium）原理、参数与部署
内容提要
2024年8月，NIST发布三项后量子密码标准FIPS 203/204/205，格基密码成为后量子时代公钥基石。文章详解ML-KEM与ML-DSA，涵盖LWE、Module-LWE数学基础，以及NTT、Fujisaki-Okamoto变换、Fiat-Shamir with Aborts等核心构造，并分析安全性、侧信道与实现优化。选型建议采用ML-KEM-768配ML-DSA-65，与X25519/ECDSA混合部署，主要代价是密钥与签名尺寸膨胀。
延伸解读
尺寸膨胀：后量子迁移的主要代价
文章明确指出，ML-KEM-768公钥1184字节、密文1088字节，ML-DSA-65签名3309字节，约为Ed25519签名的52倍。对现代互联网应用，TLS握手多传1-2KB可以接受；但对低带宽物联网设备，如64KB RAM、0.3kbps LoRa节点，仅传输一次公钥就需约30秒。因此，部署时需权衡场景：数据中心可平滑迁移，边缘设备则面临质变挑战。
混合部署：安全过渡与工程代价
文章建议采用ML-KEM-768配ML-DSA-65，并与X25519/ECDSA组成混合方案。Chrome、Cloudflare默认启用的TLS组X25519MLKEM768即为例证。混合模式提供双保险，但代价是ClientHello膨胀至1216字节，常跨越多个TCP段，导致部分中间设备处理失败。Chrome曾提供企业策略开关临时关闭后量子密钥交换，这揭示了混合模式并非免费午餐。
安全争议：参数选择与攻击估计
文章指出，ML-KEM-512是否达到NIST Level 1曾有公开争论，因core-SVP估计仅118-124比特，低于Level 1的143比特门槛，但core-SVP是保守简化指标，不能直接比较。此外，理想格的结构性攻击风险存在争议，部分密码学家对长期安全性持谨慎态度。因此，部署方普遍选ML-KEM-768而非512，并为未知攻击留出余量。
实现要点：常量时间与侧信道防护
文章强调，ML-KEM和ML-DSA的侧信道防护是实现方责任。解封装涉及秘密与密文乘法，需防功耗分析；ML-DSA拒绝采样循环的中间值不能泄露。FIPS 203/204要求秘密中间值用完即清除，工程上需常量时间操作，如密文比对用逐字节异或而非memcmp，隐式拒绝的密钥选择用条件拷贝而非分支。这些细节直接影响部署安全性。
Q&A
ML-KEM和ML-DSA分别基于什么数学问题？
两者都基于模格上的带误差学习问题（Module-LWE）。ML-KEM是密钥封装机制，ML-DSA是数字签名算法，它们共享相同的代数框架和底层运算原语。
ML-KEM-768和ML-DSA-65的密钥与签名尺寸是多少？
ML-KEM-768公钥1184字节、密文1088字节；ML-DSA-65公钥1952字节、签名3309字节。ML-DSA-65签名约为Ed25519签名的52倍。
为什么ML-KEM使用NTT？NTT有什么作用？
NTT（数论变换）用于加速多项式乘法，将朴素O(n^2)的乘法降至O(n log n)。ML-KEM的模数q=3329使得Z_q中存在256阶本原单位根，从而将多项式环完全分裂为128个二次因子，实现高效运算。
Fujisaki-Okamoto变换在ML-KEM中起什么作用？
FO变换将IND-CPA安全的公钥加密方案提升为IND-CCA2安全的KEM。它通过重新加密验证密文完整性，并采用隐式拒绝策略，避免信息泄漏。
ML-DSA签名中为什么需要拒绝采样？
拒绝采样用于消除签名中z=y+c·s₁对秘密s₁的信息泄漏。只有当z的分布与y的原始分布足够接近时，签名才被接受，从而保证安全性。
部署后量子密码时，混合方案（如X25519MLKEM768）有什么好处和代价？
好处是双保险：即使格基方案被攻破，X25519仍提供传统安全性；反之亦然。代价是ClientHello变大（密钥份额1216字节），可能超过单个TCP段，导致中间设备处理失败。
ML-KEM-512是否达到NIST安全级别1？
存在公开争论。ML-KEM-512的core-SVP估计为118-124比特，低于Level 1的143比特门槛，但core-SVP是保守简化指标，不能直接比较。NIST认为计入内存代价后仍可达Level 1，但裕度不大。
ML-KEM和ML-DSA在实现中如何防御侧信道攻击？
要求所有秘密相关操作常量时间，使用位运算而非条件分支；比较操作使用逐字节异或；隐式拒绝的密钥选择用常量时间条件拷贝；避免依赖秘密的查表。
