CRYSTALS-Dilithium 与 Falcon 签名

RSA 和 ECDSA 签名会被 Shor 算法破解。后量子签名必须在以下场景中替代它们：TLS 证书、代码签名、电子邮件签名（S/MIME、PGP）以及软件更新身份验证。NIST 已将两种基于格的方案标准化：ML-DSA 和 FN-DSA。

Dilithium 的安全性基于模-LWE 和模-SIS（短整数解）问题的困难性。其安全性证明基于 QROM（量子随机预言机模型）。它有三种变体：Dilithium2（约 128 位）、Dilithium3（约 192 位）和 Dilithium5（约 256 位）。签名路径简单，且无需拒绝采样。

私钥：秘密矩阵 s1、s2。公钥：t = As1 + s2。签名：随机采样 y；计算 w = Ay；计算挑战值 c = H(mu || w1)，其中 w1 = HighBits(w)；计算 z = y + cs1；如果 ||z|| 或 ||r0|| 过大，则拒绝并重试。输出 (z, c, hint)。

验证 (z, c, hint)：检查 ||z|| 是否足够小；计算 w' = Az - ct；使用 hint 恢复 w1；验证 c == H(mu || w1)。hint 是 MakeHint() 生成的少量比特。拒绝操作可以确保 z 不会泄露 s1，其安全性论证称为“中止后均匀”论证。

ML-DSA-65（Dilithium3，192 位安全强度）：公钥 1952 字节，私钥 4000 字节，签名 3293 字节。相比之下，ECDSA-P256 的公钥为 64 字节，签名为 64 字节。Dilithium 的签名大约大 40—50 倍，但可以抵抗量子攻击。

Falcon 基于 NTRU 格，并在 NTRU 格上使用高斯采样器。它的签名明显小于 Dilithium，但签名过程需要浮点高斯采样器，因此更难实现为常数时间，也更难编写安全的代码。

Falcon-512（128 位安全强度）：公钥 897 字节，签名 666 字节，远小于 Dilithium。代价是 Falcon 更难安全地实现（高斯采样容易受到时序攻击）。它适合带宽受限的环境，但需要谨慎实现。

SPHINCS+ 是一种基于哈希的签名方案，不依赖结构性代数假设，是一种保守的选择。其安全性仅依赖哈希函数的安全性。签名大小约为 8—50 KB，较大；签名速度较慢。它适用于长期信任至关重要而性能处于次要地位的场景。

ML-DSA（Dilithium）：通用、实现简单，适合 TLS 证书和代码签名。FN-DSA（Falcon）：适合带宽受限的环境（IoT、LPWAN）。SLH-DSA（SPHINCS+）：极其保守，适合长期使用的根密钥（CA 离线密钥、软件信任根）。

Dilithium：拒绝采样可能通过分支时序泄露信息，请使用常数时间比较。Falcon：高斯采样器使用浮点数，请确保 FP 的确定性。两者都应避免多项式运算中的侧信道。请使用 NIST 提交包中的参考实现。

NIST FIPS 204：ML-DSA（Dilithium）。NIST FIPS 205：SLH-DSA（SPHINCS+）。NIST FIPS 206：FN-DSA（Falcon）。这些标准均于 2024 年 8 月发布。相关库包括 OpenSSL 3.x、BoringSSL 和 liboqs（Open Quantum Safe 项目），它们都实现了这三种方案。

Falcon 相比 Dilithium 的主要优势是什么？

ML-DSA（Dilithium）：基于格、实现简单，签名约为 3 KB。FN-DSA（Falcon）：基于 NTRU，签名约为 700 字节，但实现复杂。SLH-DSA（SPHINCS+）：基于哈希、较为保守，但签名较大。三者均已在 FIPS 204/205/206 中标准化。下一节：使用混合方案迁移到 PQC。