基于同源密码学的未来

2022 年 7 月 Castryck-Decru 对 SIKE 的攻破极大地改变了同源密码学领域。在这次攻破之前，基于同源的密码学是一个很有前景的后量子方向，具有较小的密钥尺寸，标准化工作活跃，研究社群也在不断壮大。SIKE 失守之后，该领域不得不重新审视其基础。关键问题是：在出现新的 Richelot 同源技术之后，基于同源的密码学中哪些方面仍然困难？目前看来，基于自同态环的困难性（SQISign 使用）以及可交换类群作用（CSIDH）仍然成立。被攻破的是 SIDH 特有的辅助挠点泄露，而不是同源技术本身。

SQISign（短四元数与同源签名，De Feo 等人，2020 年）是目前已知最紧凑的后量子签名方案。公钥：64 字节（一个超奇异 j 不变量）。Level 1 的签名：177 字节。相比之下，Level 2 的 ML-DSA（Dilithium）公钥为 1312 字节，签名为 2420 字节。SQISign 的安全性基于 Deuring 对应：在两个给定的超奇异曲线之间计算指定次数的同源，等价于在自同态环四元数代数中寻找一个理想。SQISign 在这一困难问题上使用 Fiat-Shamir 身份识别方案，将签名生成​​为响应同源的压缩表示。

SQISign 的紧凑性伴随着严重的性能损失。签名过程需要使用四元数代数中的从理想到同源的转换，计算一个次数很大的同源（约为 p^{1/4}）；根据参数集不同，这项计算密集型操作在桌面 CPU 上大约需要 60-600 秒。验证速度更快（约 200 毫秒），但仍远慢于 ML-DSA 的验证（微秒级）。SQISign 2.0（2023 年）通过算法改进将性能提升了 100 倍，使签名耗时降至 1-10 秒。SQISign HD（高次数）及其他变体仍在持续优化。其目标应用是带宽严重受限的场景（物联网证书、区块链数据、空间通信），在这些场景中计算速度的重要性低于数据尺寸。

FESTA（基于超奇异挠点攻击的快速加密，2023 年）是一种专门设计来避免 SIDH 式挠点泄露的 KEM。其关键设计思路是：不同于 SIDH 中发布 phi_A(P_B) 和 phi_A(Q_B)，FESTA 使用另一种同源结构，其中加密方的公钥仅为像曲线（不包含挠点像）。FESTA 以改进的方式使用 2^n-同源，使解密无需获得通信对方的挠点基像。初步分析表明，由于辅助信息结构不同，FESTA 能够抵御 Castryck-Decru 攻击。FESTA 是一个很有前景的方向，但仍需要更多密码分析研究——SIKE 意外失守之后，同源密码学社群对此保持谨慎。

SCALLOP（具有大定向素数的可扩展可交换作用，2023 年）旨在应对 CSIDH 的量子安全性弱点。CSIDH 使用的较小素数 p = 512 位，因此仅具备约 65 位量子安全性（受 Kuperberg 亚指数算法影响）。SCALLOP 使用不同的代数结构：具有大虚二次序复乘的曲线，其类群经过专门设计，可以抵抗 Kuperberg 式量子攻击。SCALLOP 通过更大的有效类群，在比 CSIDH-5000 更小的参数规模下达到 128 位量子安全性。代价是：SCALLOP 的代数构造更加复杂，所接受的独立分析也少于 CSIDH。

鉴于同源方案具有独特的紧凑性（SQISign 的签名为 177 字节，CSIDH 的密钥为 64 字节），并且其困难性假设与基于格的方案不同，混合构造将同源组件与格组件结合起来，以实现纵深防御。一种混合 KEM 可以同时使用 ML-KEM-512 AND CSIDH-512 进行封装，再将两个秘密一起进行哈希。要攻破组合密钥，就必须同时攻破 ML-KEM（LWE 困难性）和 CSIDH（类群作用）。只要其中任意一个仍未被攻破，混合方案就是安全的。这种密码敏捷性方法受到 NIST 和 NSA 的认可，适用于希望获得超出任何单一后量子密码原语的额外保障的组织，尤其是在量子计算机出现时间尚不确定的情况下。

基于同源的零知识证明是一个新兴的研究方向。同源路径问题（给定两条曲线，求 phi: E -> E'）可以作为知识证明方案中的困难问题。“我知道从 E 到 E' 的一个同源”这一 Sigma 协议能够在不泄露同源的情况下实现身份验证。Vero（2022 年）展示了一个实用的基于同源的 ZK 证明系统。这些 ZK 证明天然十分紧凑（命题仅由两个 j 不变量组成），但目前速度太慢，无法实际部署。随着同源计算性能的提升，在重视假设多样性的场景中，基于同源的 ZK 证明可能成为基于格或基于哈希的证明的替代方案。

同源技术不仅与后量子密码学相关，在经典椭圆曲线密码学中也有应用。用于计算椭圆曲线上点数的 Schoof-Elkies-Atkin（SEA）算法使用同源来计算弗罗贝尼乌斯迹，从而能够高效生成安全的椭圆曲线参数。同源还出现在改进 Pollard rho 算法、计算 ECDLP 的方法中。用于构造指定阶数曲线的 CM（复乘）方法使用类多项式，而类多项式从根本上说就是同源对象。基于同源的密码分析工具（寻找光滑次数的同源路径）可用于评估提议的椭圆曲线参数是否存在隐藏后门——这与 Dual EC DRBG 相关担忧直接相关。

截至 2024 年，还没有任何基于同源的方案获得 NIST 或其他主要机构的标准化。NIST 的 PQC 流程已经将 ML-KEM、ML-DSA、SLH-DSA 和 FN-DSA 标准化；这些方案全部基于格或哈希。NIST 正在开展第二轮 PQC 签名评估；SQISign 已提交参评，但面临性能方面的担忧。同源密码学社群正致力于开发更加成熟的 SQISign 3.0，使签名耗时达到实用水平（目标是低于 1 秒）。ISO 和 ETSI 尚未标准化任何同源方案。近期最有可能的标准化路径是：将 SQISign 用于需要最小签名尺寸的特定应用，可能作为信息性标准，而不是强制性原语。要实现广泛部署，仍需要数量级的性能提升。

截至 2024 年，基于同源的密码学中活跃的研究方向包括：（1）SQISign 变体（SQISign 2.0、HD、Fast SQISign），将签名性能提升至接近亚秒级。（2）CSIDH 及其变体的量子安全性分析——进一步精确估计 Kuperberg 攻击的复杂度，并探索能够抵抗该攻击的代数结构。（3）新的困难性假设——超奇异自同态环计算、虚二次环上的模问题。（4）基于同源的不经意伪随机函数，以及其在隐私保护协议中的应用。（5）同源算术的硬件实现——利用 FPGA 的并行能力实现 CSIDH 的类群作用。（6）将基于同源的群作用与通用群作用密码学框架相结合，用于构建新的函数加密和基于属性的方案。

SIKE 被攻破可能会让人想要彻底放弃基于同源映射的密码学。但密码学界持相反看法：这次破解之所以有价值，正是因为它明确指出了哪些结构不安全（SIDH 的扭点泄露），以及哪些结构仍然难以攻破（自同态环、类群作用）。研究同源映射仍然很重要，原因包括：(1) 后量子多样性——拥有格密码之外的安全性假设，可以在 LWE 被攻破时降低系统性风险；(2) SQISign 提供了目前无可匹敌的超紧凑签名；(3) 同源映射技术有助于椭圆曲线密码分析和参数验证；(4) 相关数学既优美又富有成效——为破解 SIKE 而开发的工具，直接加深了我们对椭圆曲线自同态环的理解，而这些自同态环也应用于其他领域。

SQISign 签名所依据的困难性假设是什么？

SIKE 在 2022 年被攻破后，同源映射密码学通过不同的困难性假设继续发展。SQISign 基于自同态环问题的困难性，提供了 177 字节的后量子签名（已知最小的签名）；其性能正在提升，目标是将耗时降至 1 秒以内。FESTA 针对 SIDH 的扭点泄露进行设计，用于密钥封装机制。SCALLOP 通过带定向的曲线实现 128 位量子安全性。同源映射与格密码的混合方案提供了多样化的安全性假设。目前还没有同源映射方案实现标准化。SQISign 的标准化最有可能成为近期的发展方向。SIKE 的破解加深了人们对同源映射协议中必须隐藏哪些信息的理解，也产生了可用于整个椭圆曲线密码学领域的新数学工具。