大型量子计算机一旦出现，将能破解当前互联网广泛使用的非对称加密算法。目前它们还未存在。2022年，NIST宣布了PQC竞赛中的最终密钥交换和签名方案，标志着互联网向后量子加密的转变开始。关于各种算法和标准化流程的讨论已经很多。
普遍的看法是，向后量子加密的过渡需要很长时间，因此即使量子计算机还未真正出现，我们也要开始标准化并部署相关技术。NIST竞赛的结果将被采用。
然而，关于NIST标准化的方案是否足够在公共网络上部署的问题却没有充分讨论。我们需要更优的算法，特别是那些在网络传输中占用更少字节的：嵌入在TLS ClientHello中的密钥交换方案应小于一个MTU（最大传输单元），与ECDSA性能相当但大小不超过RSA-2048的签名方案，以及可处理大公钥的小于100字节的签名。
我们来探讨一下HTTPS中加密的现状。在公开网络上的HTTPS中，加密主要用于五个方面：
- 对称加密/解密：HTTP/2的数据通过TLS连接中的认证密码（如AES-GCM）进行传输，这在很大程度上已能抵御量子计算机。
- 密钥协商：对称加密需要密钥，密钥协商是双方共同生成密钥的过程。在TLS 1.3中，通常使用椭圆曲线 Diffie-Hellman进行密钥协商。所有非量子安全的密钥交换机制，包括Diffie-Hellman，都会被量子计算机破解。
- 服务器身份验证：服务器通过X.509证书进行身份验证。至少，服务器证书包含公钥和中间证书的签名。中间证书又包含另一个公钥及其根证书的签名。公开Web PKI依赖于受信任的证书颁发机构来验证域名所有权。
- 发行透明度：Web PKI依赖于公开记录的证书，服务器确认证书已包含在记录中，这有助于防止恶意证书颁发。服务器通过提供至少两个签名证书时间戳（SCT）来实现透明度。
- 握手认证：在TLS握手期间，需要将服务器的身份绑定到连接上。在TLS 1.3中，这通过服务器证书中的公钥在“CertificateVerify”消息中的签名来实现。
当前的量子威胁主要体现在“现在收集，未来解密”的攻击中。为了防御，我们只需确保密钥协商和对称加密是“量子安全”的。幸运的是，对称加密已经足够安全，所以只需要更新密钥交换算法为量子安全版本即可。
HTTPS中剩下的加密用途——服务器身份、发行透明度和握手认证——最终需要转向量子安全版本。在当前TLS架构中，这意味着替换所有签名为量子安全版本。尽管这同样重要，但不如密钥交换紧迫。
浏览器已经开始部署量子安全的密钥交换算法，如X25519（客户端和服务器各传输32字节）和NIST竞赛的密钥交换赢家ML-KEM（客户端发送1,184字节，服务器发送1,088字节）。然而，没有主流浏览器开始部署量子安全签名。
原因在于量子安全签名及其对应的公钥过大。HTTPS握手通常涉及5个签名和2个公钥：
- 叶子证书包含1个网站的签名公钥和1个来自中间证书的签名。
- 中间证书包含1个用于验证叶证书签名的签名公钥，以及1个验证根证书签名的公钥，用于验证中间证书的真实性。根证书及其嵌入的公钥预分发给客户端。
- 握手本身包含由叶证书公钥对应的私钥签署的1个签名。
- 每个SCT包含1个签名，验证签名的公钥预分发给客户端。大多数证书有2个SCT，因此额外需要2个签名。
目前TLS中密钥和签名的大小大致如下：
- 根证书通常包含RSA密钥，中间证书也如此。根证书预分发，而中间证书由服务器提供，与叶证书一起。一个RSA中间证书的签名是4096位（512字节），公钥是2048位（256字节）。
- ECDSA叶证书的公钥是32字节，来自中间的RSA签名是256字节。
- 握手包含64字节的ECDSA签名。
- 每个SCT包含64字节的ECDSA签名。
总计，一个标准TLS HTTPS握手中的签名和公钥大小约为1,248字节。NIST PQC竞赛的赢家ML-DSA（Dilithium）是唯一适合TLS的签名算法，但其1,312字节的公钥和2,420字节的签名使得单个ML-DSA公钥就比当前HTTPS连接中所有5个签名和2个公钥还要大。直接替换现有签名算法为ML-DSA会导致TLS握手包含14,724字节的签名和公钥，这是当前的10倍多。
在没有大规模量子计算机的情况下，仅为了建立连接就发送如此大量的数据是不可持续的。作为基本的检查，我们不应该仅在签名和公钥中就发送超过3.5英寸软盘的1%。
从实际影响来看，Cloudflare发现服务器响应中每增加1千字节的数据，HTTPS握手的中值延迟会增加约1.5%。而Chrome在部署ML-KEM后，ClientHello的TLS握手延迟增加了4%，因为额外的1千字节超过了互联网标准的MTU（约1400字节），导致ClientHello被分片为两个底层传输层（TCP或UDP）包。
如果ML-KEM成为常态，为了将后量子加密对总延迟的影响控制在10%以下（假设为10%），我们需要服务器响应中额外的认证信息控制在约4千字节内。不幸的是，单个ML-DSA签名/公钥对就大约是4千字节。在量子威胁还未明确的时间线上，ML-DSA太大，无法部署。
有一些积极的进展：NIST意识到签名过大，正举办后续竞赛以寻找更小、更快的签名方案。目前的参赛者还未达到目标，但有些方案有潜力：
- Unbalanced Oil and Vinegar (UOV)：UOV的公钥很大（66千字节），但签名只有94字节，与当前SCT中的ECDSA签名相当。66千字节的公钥大小可以接受，因为证书透明度日志的公钥是预分发的，且日志数量较少（约10个）。然而，UOV不适用于根证书，因为根证书过多，嵌入到二进制文件中会过大。
- SQISign：SQISign的公钥是64字节，签名是177字节。如果用于证书和握手签名，将是264 + 3177 = 659字节，优于当前的RSA+ECDSA组合！但SQISign的性能极差，需要10,000倍的签名速度提升和100倍的验证速度提升。
- Mayo：Mayo可能可行。Mayo1的公钥是1,168字节，签名是321字节，适合用于证书和握手认证（1,1682 + 3213 = 3,299字节）。Mayo2的公钥为5,488字节，但签名只有180字节，如果UOV不可行，它可以用于SCTs。
还有其他性能调整的可能，但它们都需要对HTTPS、TLS和Web PKI交互方式做出较大改动，而不仅仅是直接替换为PQC算法。
- 中间证书预分发：预先分发已知的中间证书可以为平均中间证书节省约1.5千字节。这不会从根本上改变NIST候选方案的可行性，但可能帮助Mayo保持在当前可行范围内。
- 合并SCTs和证书：如Merkle-Tree Certificates的实验性提议将证书和SCTs合并为一个单一的对象，只包含基于哈希的证明。这将减少握手需要的单个签名和Merkle-tree证书中的单个公钥，以及哈希包含证明。不幸的是，这可能对非浏览器应用不太可行，如需要延迟（每小时）批量发布并要求客户端与透明度服务器保持同步。
对于浏览器客户端，这种形式的解决方案可能是性能优化，但对于非浏览器客户端可能不可行。然而，握手延迟对非浏览器客户端的影响较小。
- 缩小根存储的大小：一个包含少于10个UOV公钥的后量子根存储将接近当前根存储的量级。
综上所述，结合Mayo、UOV和其他PKI改进，可能足以在Web PKI中实现量子抵抗的认证。然而，所有这些设计仍面临风险：
- 性能影响可能比Cloudflare测量的更大。
- 该实验可能主要针对理想条件（桌面企业的用户访问登录页面），由低延迟边缘服务器提供服务。
- Mayo和UOV的安全性可能无法保证。这并非首次有前景良好的量子算法被发现有漏洞。
10%的性能影响可能太大，除非量子计算机真的迫在眉睫。
为了降低风险，我们需要提高信任锚的灵活性、抑制中间证书数量并进行PKI迁移。这些措施已经在进行中。
为了使后量子过渡更可行，我们需要找到性能不逊色于RSA-2048的算法，具体要求如下：
- 与TLS ClientHello其他部分一起，嵌入到单个MTU内的后量子密钥交换方案。
- SQISign（或具有类似特性的新算法）的10,000倍签名速度提升和100倍验证速度提升。
在某种程度上，这可能是不切实际的。但当前以ML-DSA的形式应用于Web PKI也是不可能的。
注意：虽然有人可能认为量子威胁不那么重要，但这不是本文讨论的重点。无论量子威胁的重要性如何，密钥交换和认证同样至关重要，两者都会被大型量子计算机破解。