SIDH 与 SIKE：设计与密码分析

超奇异同源映射 Diffie-Hellman（SIDH）由 Jao 和 De Feo 于 2011 年提出，是一种类似于 Diffie-Hellman、但使用超奇异椭圆曲线上的同源映射的公钥交换协议。双方从 Fp2 上的同一条超奇异曲线 E 开始。Alice 计算秘密同源映射 phi_A: E -> E_A（2^a-扭点中的随机核），并公开 E_A 以及 Bob 的扭点生成元在 phi_A 下的像。Bob 计算 phi_B: E -> E_B（3^b-扭点中的随机核），并公开 E_B 以及 Alice 的扭点生成元在 phi_B 下的像。Alice 使用 Bob 公开的数据计算 phi_A': E_B -> E_AB；Bob 计算 phi_B': E_A -> E_AB。双方最终都得到 j(E_AB) 作为共享秘密。

SIDH 的特殊素数形式 p = 2^a * 3^b * f - 1（f 是用于保证素性的较小余因子）确保 Fp2 上的曲线 E 具有所需的扭点结构。对于 SIKEp434（NIST 1 级，128 位后量子安全性）：p = 2^216 * 3^137 - 1，a = 216，b = 137。这意味着 Alice 要进行 216 步 2-同源映射，Bob 要进行 137 步 3-同源映射。密钥大小：Alice 的公钥由 E_A 加上两个 Fp2 点（phi_A(P_B)、phi_A(Q_B)）组成，即 3 * 2 * 54 = 324 字节。SIKEp751 的目标是 192 位经典安全性和 128 位量子安全性，公钥大小为 564 字节。这些是所有 NIST PQC 候选方案中最小的公钥，但代价是速度慢 100 到 1000 倍。

SIKE（超奇异同源映射密钥封装）是一个基于 SIDH、使用藤崎-冈本变换构建的 IND-CCA2 安全 KEM。SIKE.Encaps：随机选择消息 m，计算（c0 = 使用种子 m 生成的 SIDH 公钥，c1 = H2(m) XOR pk），发送（c0、c1）。SIKE.Decaps：使用秘密密钥从 c0 恢复 m，验证 c1，重新计算（c0、c1）以检查一致性，并输出 K = H3(m, c0)。FO 变换将 CPA 安全的 SIDH 交换转换为 CCA2 安全的 KEM。SIKE 参加了 NIST PQC 在 2017 年至 2022 年间的全部四轮评选，在经历广泛密码分析后仍然存活，直到 2022 年 7 月出现了毁灭性的经典攻击。

从 2011 年到 2022 年，SIDH 经受住了大量密码分析工作。已知针对 SIDH 的最佳攻击包括：(1) 通用 SSIP 算法：经典计算下的复杂度为 O(p^{1/4})，使用 Tani 算法时量子计算下的复杂度为 O(p^{1/6})。(2) 对同源映射路径的中间相遇攻击：经典计算下的复杂度为 O(p^{1/4})，与 SSIP 相同。(3) 针对特定结构性攻击的多项式时间算法（van Oorschot-Wiener）：不适用于 SIDH。数十篇论文分析了 SIDH 的安全性，在 11 年间没有发现经典或量子多项式时间攻击。这一记录使 SIKE 成为可信的 NIST 入围方案。最终的攻破并非来自对 SSIP 的直接攻击，而是利用了 SIDH 的辅助扭点信息。

2022 年 7 月 30 日，Wouter Castryck 和 Thomas Decru 发布了一篇预印本，展示了针对 SIDH 的经典多项式时间攻击。该攻击利用 SIDH 辅助扭点 phi_A(P_B)、phi_A(Q_B) 中的额外信息：这些信息实际上揭示了 phi_A 在 3^b-扭点子群上的作用。结合像曲线 E_A，这使得攻击者能够利用复乘椭圆曲线理论和 Richelot 同源映射中的技术，重构 phi_A 的核（从而重构 phi_A 本身）。在 SIKEp434 上，该攻击仅用一台笔记本电脑运行了 62 分钟，而这一参数集原本被认为可以提供 128 位后量子安全性。几天之内，独立研究人员就确认并扩展了针对所有 SIDH 参数的攻击。

SIDH 的设计要求双方公开对方扭点基点在其秘密同源映射下的像。这是协议正常工作的必要条件：如果没有 phi_A(P_B) 和 phi_A(Q_B)，Bob 就无法将自己的同源映射传送到 Alice 的曲线上，从而计算共享秘密。但这部分额外信息——它揭示了 phi_A 限制在 3^b-扭点上的作用——最终被证明包含了远超预期的大量信息，后果具有灾难性。Castryck-Decru 攻击使用亏格为 2 的曲线（Richelot 同源映射），将问题提升到更高亏格的对象上；在这些对象中，受限作用可以完全确定 phi_A。这种信息泄露是 SIDH 的结构性问题，除非改变协议的根本设计，否则无法修复。

2022 年 7 月 5 日（早于 Castryck-Decru 攻击），NIST 宣布了其最初选择进行 PQC 标准化的方案：ML-KEM（Kyber）、ML-DSA（Dilithium）、SLH-DSA（SPHINCS+）和 FN-DSA（Falcon）；SIKE 不在其中（它当时处于第二轮评选阶段）。2022 年 7 月的 Castryck-Decru 攻击促使 NIST 正式完全取消对 SIKE 的考虑。NIST 声明：“SIKE 不再被纳入标准化考虑。”这是 NIST PQC 竞赛中最具戏剧性的密码分析进展，表明即使一种方案经受住了 11 年的分析，也可能因全新的根本性数学洞见而被攻破。

Castryck-Decru 攻击发布后一周内，Thomas Decru 和 Luciano Maino（彼此独立）以及之后的 Damien Robert 都发布了进一步的改进。Robert 的攻击变体使用了相同的洞见，但计算的是 E_A 的自同态环，而不是直接计算同源映射的核；从数学描述的角度看，这种方法可以说更为简单。这些迅速出现的独立重新发现证实，Castryck-Decru 攻击揭示的是一种根本性的结构弱点，而非晦涩的技巧。后续论文的快速发表也反映出，许多研究人员一直在研究 SIDH 的扭点泄露，将其视为潜在的攻击途径；他们意识到这是不同寻常的信息披露，却一直无法加以利用，直到 Castryck 和 Decru 找到了通往亏格为 2 的桥梁。

FESTA（来自超奇异扭点攻击的快速加密，2023 年）是一种受 SIDH 启发、但避开扭点辅助数据的 KEM 设计。FESTA 使用了不同的协议结构：公钥不包含对方扭点基点的像，而是仅通过像曲线对秘密同源映射作出承诺（不包含辅助点）。FESTA 使用同源映射进行加密，并以一种泄露较少结构信息的方式工作。早期安全性分析表明，FESTA 可以避开 Castryck-Decru 攻击所利用的结构。不过，FESTA 较新，所接受的审查少于 SIKE 11 年的安全记录；在进行广泛分析之前，同源映射研究群体对于部署新方案仍然保持谨慎。

SIKE 被攻破带来了重要经验。(1) 披露辅助信息十分危险：SIDH 的额外扭点数据虽然是协议所必需的，却致命地泄露了信息。协议设计者必须分析每一项公开数据，而不仅仅是主要数值。(2) 既有记录不是安全性证明：11 年没有已知攻击令人安心，但并不能构成保证。将安全性归约到定义明确的困难问题上的密码学证明，比诉诸权威或仅凭经受住审查的经历更加可靠。(3) 新颖的数学工具会带来风险：Castryck-Decru 攻击使用了亏格为 2 的 Richelot 同源映射，这是一种此前未用于同源映射密码分析的数学工具。研究新型原语的密码分析人员必须考虑新的数学领域。

尽管 SIKE 已被攻破，基于同源映射的密码学仍在作为一个研究领域继续发展。SQISign 签名（1 级下为 177 字节）仍然是已知最紧凑的 PQC 签名，并使用了不同的困难性假设，即自同态环问题，因此不受 SIDH 攻击影响。基于 CSIDH 的协议使用类群作用结构（可交换同源映射），不存在扭点泄露，但 CSIDH 也面临自身的挑战（速度比 SIDH 曾经的速度更慢，量子安全性分析仍在进行）。同源映射研究群体将 SIKE 被攻破视为一次学习经历，加深了对同源映射协议中必须隐藏哪些信息的理解；这些知识对于设计未来方案十分宝贵。

SIDH 的哪一项设计使 Castryck-Decru 攻击成为可能？

SIDH 在双方之间使用交替的 2^a 和 3^b 同源映射链，并共享辅助扭点的像，以实现密钥交换。SIKE 使用藤崎-冈本变换封装 SIDH，从而提供 CCA2 安全性。SIKE 拥有所有 NIST PQC 候选方案中最小的密钥（374 字节），但速度慢 100 到 1000 倍。经过 11 年的安全性检验后，Castryck-Decru 在 2022 年 7 月利用亏格为 2 的 Richelot 同源映射，借助扭点泄露攻破了 SIKE。NIST 取消了对 SIKE 的考虑。FESTA 避免披露扭点。SQISign 继续使用自同态环困难性。SIKE 被攻破说明，必须像分析协议的主要数值一样谨慎地分析辅助公开数据。