后量子密码十字路口：格方法遇挑战，ECC仍是安全带

liumuhui 4小时前阅读数 1 #区块链

PQC 十字路口与 ECC 安全带

RSA 已经为我们服务了近五十年，椭圆曲线密码学也解决了离散对数带来的许多问题。在过去的几十年里，每当看起来 RSA 或 ECC 快要被破解时，我们只是不断提高参数。对于 RSA，我们现在使用 2,048 位的模数；对于 ECC，我们通常使用 secp256k1、NIST P256 和 Curve 25519 的 256 位曲线。但现在，有了 Shor 算法，我们无法再靠不断提升参数来应对，尤其是对 ECC 而言。对于 RSA，我们或许还能继续沿用，并不断增加模数的大小，但性能会变得非常糟糕。

于是，我们最终得到了一些对量子计算机具有一定安全性的方法：格方法（基于 Learning With Errors 方法）；多元密码学（例如 Rainbow）；同源方法（例如 SIKE）；基于编码的签名（例如 HQC 和 Classic McEliece）；以及 MPC-in-the-Head（例如 MAYO）。在 NIST 的第一轮标准化中，格方法被证明在性能与密钥/签名/密文大小之间取得了最佳平衡。在数字签名方面，NIST 批准了 Dilithium（也就是 ML-DSA）、Falcon（也就是 FN-DSA）和 SPHINCS+（也就是 SLH-DSA）；在密钥交换方面，他们选择了 Kyber（也就是 ML-KEM）和 HQC。最终，NIST 目前只确定了两种主要的格标准，并且眼下没有太多替代方案：

PQC 处于十字路口？

从 RSA 和 ECC 向基于格的方法迁移似乎一切顺利，2030 年进行评估和风险分析、2035 年全面切换的时间表看似合理。但是，我们看到新的研究日复一日地攻击格方法的核心。就在本周，我们看到一篇论文声称（可能）能在多项式时间内攻破这些方法（当然，这一点尚未得到证实）[ here][2]：

Daniel R. Simon 的工作实际上开创了后量子密码学这一领域 [ here][1]（见下文），并且现在提出了一种多项式时间量子算法，用于解决二面体陪集问题（Dihedral Coset Problem）——该问题现已与 Module-LWE（定义 ML-KEM 的基本困难问题）联系起来 [3][ here]。如果该算法被证实，将产生一种针对近似最短向量问题和 LWE（Learning With Errors）的多项式时间量子算法，而 LWE 正是许多用于抗量子密码学的格方法的基础。

虽然该方法是否真的被攻破仍未得到证实（因为它尚未经过同行评审），但令人担忧的是，这可能只是众多论文中的第一篇，而这些论文可能会破坏格方法作为“困难问题”的基础。顶尖研究人员也表达了同样的忧虑：

Daniel 指出，我们仍然需要将 ECC 作为安全带，签名和密钥交换方法或许应该采用混合方式，这样即使格方法失效，我们仍有可靠的椭圆曲线方法来保护自己。总体而言，这正是 ML-KEM-768/X25519 等混合方法的工作方式，即其安全性等同于其中最强的方法。对于 TLS 握手，基本流程如下 [ here]：

而使用 X-Wing 的流程如下 [ here]：

移除安全带？

但正如 Daniel 所指出的，ECC 只是一条安全带，用来防止我们暴露出大规模漏洞。真正的长期解决方案是寻找具有更强长期基础的其他替代方法。Bernstein 最近演示了在一秒钟内恢复 ML-DSA 密钥，并指出单独部署 ML-DSA 可能会显著削弱安全性 [ here]：

为此，我们或许需要考虑使用基于哈希的签名方法 SLH-DSA 来承担长期签名，而 ML-DSA 只用于短期（或许仅几个月）。这意味着数字证书中可能包含实体的 ML-DSA 公钥，但证书上的实际签名将使用 SLH-DSA。为什么？因为基于哈希的方法通常对攻击具有鲁棒性。另一个正在形成的计划是摆脱数字证书（X.509），将公钥方法建立在 Merkle 树之上（这种方法使用基于哈希的方法）。对于 ML-KEM，人们担心直接将其用于密钥交换（或者更准确地说，作为密钥封装方法），因为一旦该方法被破解，所有受其保护的流量都将暴露。这可能会以 Heartbleed 差点做到的方式，暴露整个互联网。

记住我，以便更快登录

对于签名方法，我们至少还有一个替代方案 SLH-DSA，但相比之下，它通常比 ML-DSA 慢。虽然它的公钥很小，但签名大小相对较大。因此，NIST 开启了一轮新的评估，寻求将其他方法标准化。当前的候选名单是：

多元签名（4）：MAYO、QR-UOV、SNOVA 和 UOV（Unbalanced Oil and Vinegar）。
MPC-in-the-Head 签名（5）：MIRA/MiRitH（MinRank in the Head）、MQOM（MQ on my Mind）、PERK、RYDE 和 SDitH（Syndrome Decoding in the Head）。
基于格的签名（1）：HAWK。已移除！
基于编码的签名（2）：CROSS（Codes and Restricted Objects Signature）和 LESS（Linear Equivalence）
基于对称的签名（1）：FAEST。
同源签名（1）：SQIsign。

不幸的是，HAWK 已经因其底层方法的弱点而遭到淘汰：

第 2 轮评估中的许多方法都包含在 liboqs 库中 [ here]：

SIKE（基于同源）和 Rainbow（多元密码学）在上一轮评估中都被破解；而在最新的第 2 轮评估中，同源和多元密码学仍有很好的代表性。希望研究人员已经普遍学会了如何为这些方法挑选最佳参数，从而加以改进。MAYO 就是这些方法之一，它通常具有良好的签名性能，密钥和签名大小也合理：

MAYO-1
Public key size: 1420
Private key size: 24
Signature size:  454

对于密钥交换方法，NIST 正在推动 HQC 作为替代方案，但其他方法仍可能在一般使用中脱颖而出 [ here]：

应当记住，NIST 并不是标准化领域唯一的参与者，ISO 已经将 NIST 通常不考虑的其他方法标准化并投入使用，这包括用于密钥交换的 FrodoKEM 和 Classic McEliece。

结论

因此，我们仍需观察这篇新论文是否会给 ML-KEM、ML-DSA 以及整个格方法带来问题。如果它确实显示出弱点，那么我们几乎还没有越过起跑线，就已经面临一个亟待解决的大问题。唯一确定的是，在不久的将来我们需要 ECC 这条安全带，因为目前还不能真正信任格方法的长期安全性。实现漏洞也可能给新方法造成问题，而现有的 RSA 和 ECC 库通常对实现攻击具有鲁棒性。

如果出现问题，也许我们可以修复，但可能还有其他方法能提供长期解决方案——然而，这个方案不太可能只靠单一方法。我们很幸运拥有 ECC，因为它解决了我们许多核心的信任和隐私问题，但未来，我们需要一系列方法来妥善保护互联网（当然，还有公民的数据）。

基本上，我们需要屏住呼吸，观察 LWE 是否已被破解，同时继续努力向量子鲁棒方法迁移。

参考文献

[1] Simon, Daniel R. "On the power of quantum computation." SIAM Journal on Computing 26.5 (1997): 1474–1483. https://ieeexplore.ieee.org/document/365701

[2] Daniel R. Simon, A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem, Cryptology ePrint Archive, Paper 2026/1591. https://eprint.iacr.org/2026/1591.

[3] Wen, W., & Zheng, J. (2026). Module Learning with Errors and Structured Extrapolated Dihedral Cosets. Cryptology ePrint Archive. https://eprint.iacr.org/2026/155.pdf