椭圆曲线同源：数学基础

在域 k 上，两个椭圆曲线 E 和 E' 之间的同源是一个非常数有理映射 phi: E -> E'，同时也是一个群同态——它将 E 的群运算映射为 E' 的群运算。每个同源 phi 都有一个对偶同源 phi_hat: E' -> E，使得 phi_hat 与 phi 的复合等于 E 上的乘以 deg(phi) 映射。同源的次数等于其核的大小：次数为 l 的同源具有大小为 l 的核。同源推广了标量乘法：乘以 n 是从 E 到自身的同源，其次数为 n^2。在有限域上，同源可以表示为有理函数（多项式），并且能够高效求值。

Velu 公式（1971 年）提供了显式公式：给定 E 的一个子群 G，可以计算同源 phi: E -> E/G。像曲线 E/G = E' 和有理映射 phi 都由 G 完全确定。Velu 公式将像曲线的系数和有理映射计算为有理函数，其次数等于 |G|。对于阶为素数 l 的核子群 G，同源的次数为 l，可以用 O(l) 次运算计算得到。sqrt-Velu 算法（Bernstein 等人，2019 年）将大 l 的运算复杂度降至 O(sqrt(l))，从而实现了 CSIDH 高效的大素数同源计算。Velu 公式是所有基于同源的密码学方案的计算核心。

有限域 Fp 上的椭圆曲线可以组织成同源图。顶点是椭圆曲线的 j 不变量（一种规范不变量，可以确定曲线在同构意义下的形式）。边是 l-同源：对于较小的素数 l，根据 l-扭子群的结构，每条普通曲线恰好有 l+1 条向外的 l-同源。Fp 上的 l-同源图是一个 (l+1)-正则图。这些图的 Ramanujan 性质（即其为扩展图）意味着其中的随机游走能够快速混合，从而提供了基于同源的密码学所依赖的困难性假设：长度为 O(log p) 的随机游走会在 j 不变量上产生均匀分布。

Fp 上的椭圆曲线分为两类。普通曲线具有非平凡的 p-秩，这意味着存在 p^2 个同构类，并且其同源图具有火山结构（火山口和火山底）。超奇异曲线的 p-秩为 0，并且全部位于 Fp2 上一个连通的同源图中。Fp 上超奇异 j 不变量的数量约为 p/12。SIDH 和 SIKE 使用超奇异曲线，因为它们的同源图是 Ramanujan 图，具有很强的扩展性质，并且没有可能泄露游走方向的火山结构。CSIDH 也使用超奇异曲线，但使用的是 Fp（而非 Fp2），利用了不同的代数结构。

基于同源的密码学建立在两个相关的困难问题之上。超奇异同源问题（SSIP）：给定 Fp2 上的两个超奇异椭圆曲线 E 和 E'，求出同源 phi: E -> E'。计算超奇异同源问题（CSSI）：给定 E、E' = phi(E) 以及 phi 的次数，求出 phi。针对 SSIP 的最佳经典算法需要 O(p^{1/4}) 的时间。最佳量子算法（Tani 的寻爪算法）需要 O(p^{1/6}) 的时间。当 p = 2^{434} 时，这对应于 128 位的经典安全性。与 Shor 算法针对 RSA/ECC 所实现的指数级加速相比，这种量子加速明显较弱，因此基于同源的方案能够实现后量子安全。

SIDH（超奇异同源 Diffie-Hellman）使用特殊结构的素数 p = 2^a * 3^b - 1，以确保 Fp2 上的曲线 E 具有 2^a-扭点（满足 2^a * P = 0 的点集）以及可访问的 3^b-扭点。Alice 的秘密是一个 2^a-同源 phi_A: E -> E_A，其核由 2^a-扭点中的一个随机元素生成。Bob 的秘密是一个 3^b-同源 phi_B: E -> E_B。他们交换扭点的像：Alice 发布 E_A 和 phi_A(P_B)、phi_A(Q_B)；Bob 发布 E_B 和 phi_B(P_A)、phi_B(Q_A)。这样，双方都可以从对方的曲线计算同源，最终得到相同的共享 j 不变量。

椭圆曲线的自同态环 End(E) 是从 E 映射到自身的所有同源（包括标量乘法）组成的环。对于 Fp 上的普通曲线，End(E) 是一个虚二次域中的阶。对于超奇异曲线，End(E) 是一个在 p 和无穷远处发生分歧的四元数代数中的极大阶。End(E) 的结构完全决定了曲线在同构意义下的形式。自同态环问题——给定 E 计算 End(E)——被认为是困难的（对于超奇异曲线，它等价于 SSIP）。Castryck-Decru 对 SIDH/SIKE 发起的攻击利用了 SIDH 协议泄露的额外信息，从而高效地重建了自同态环的一部分，并攻破了该方案。

次数为 l 的同源 phi: E -> E' 可以表示为次数为 l 的多项式（或者利用点的逆元具有相同 x 坐标这一事实进行对称性优化后，表示为次数为 l/2 的多项式）。使用 Velu 公式计算给定点 P 的 phi(P) 需要 O(l) 次乘法。对于 l = 2^a、约为 2^216 的 SIDH，这看起来难以承受，但 SIDH 利用了这样的事实：2^a-同源可以分解为由 a 个 2-同源组成的链——每个 2-同源的计算成本都很低，而 a 步组成的链会产生一个 2^a-同源。3^b 的情况类似。sqrt-Velu 使 CSIDH 的大奇素数同源计算能够以 O(sqrt(l)) 而非 O(l) 的复杂度运行，从而使 CSIDH 具备实用性。

SIKE（超奇异同源密钥封装）曾是 NIST PQC 候选方案，在进入第四轮前通过了所有轮次，随后被攻破。SIKE 的显著特点是密钥大小为所有 NIST 候选方案中最小：SIKEp434（NIST 级别 1）的公钥只有 374 字节。相比之下，ML-KEM-512 的公钥为 800 字节。SIKE 之所以能够如此紧凑，是因为共享秘密源自单个 j 不变量（一个约 430 位的域元素）。这种紧凑性是有代价的：SIKE 的速度比其他候选方案慢 100—1000 倍。2022 年 7 月，Castryck 和 Decru 使用一种可在笔记本电脑上几分钟内运行的经典攻击攻破 SIKE 后，SIKE 立即被淘汰出 NIST 竞赛。

基于同源的密码学在后量子方法中占据独特位置。密钥大小：比基于格的方法（ML-KEM：800 多字节）或基于哈希的签名小得多（基于哈希的签名的公钥为 32—49 字节，但签名为 7856—49856 字节）。性能：比所有替代方案都慢得多（SIKE 比 ML-KEM 慢 100—1000 倍）。安全性假设：不同于 LWE（用于 ML-KEM/ML-DSA）、SIS 或哈希函数，因此提供了密码学多样性。后量子安全基础：同源路径问题目前没有已知的多项式时间量子算法，而 RSA/ECC 会被 Shor 算法完全攻破。同源困难性的基础仍在研究之中，SIKE 被经典攻击攻破便证明了这一点；相比之下，LWE 问题已经得到充分研究。

尽管 SIKE 已被攻破，基于同源的密码学仍然是活跃的研究领域。SQISign（短四元数同源签名）是一种基于同源的签名方案，签名大小为 177 字节（第 2 级的 ML-DSA 为 2420 字节），是目前已知最小的 PQC 签名。SQISign 使用的困难问题是在给定的两个超奇异曲线之间计算指定次数的同源，这一问题被形式化为自同态环问题。FESTA（基于超奇异扭点攻击的快速加密）是一种新的 KEM 设计，避免使用导致 SIDH 易受攻击的额外扭点辅助数据。CTIDH（常数时间 CSIDH）改进了 CSIDH 的性能。即使在 SIKE 被淘汰后，这些方案仍使同源研究保持相关性。

椭圆曲线之间的同源是什么？

同源是一个有理映射 phi: E -> E'，同时也是群同态，其次数等于核的大小。Velu 公式根据核子群计算像曲线和映射。同源图将曲线组织为顶点，并以 l-同源作为边，形成 (l+1)-正则 Ramanujan 图。超奇异曲线（SIDH/SIKE/CSIDH 使用）具有扩展性很强的同源图。SSIP 和 CSSI 问题构成了同源安全性的基础。SIDH 利用扭点结构以及交替的 2-同源链和 3-同源链。自同态环计算等价于 SSIP。SQISign 和 FESTA 代表了 SIKE 之后利用自同态环困难性的活跃研究方向。