CSIDH：交换超奇异同源

CSIDH（可交换超奇异同源映射 Diffie-Hellman，Castryck 等人于 2018 年提出）是一种基于同源映射的密钥交换，通过使用根本不同的代数结构，完全避免了 SIDH 的扭点泄露。CSIDH 使用 Fp 上的超奇异曲线（而不是 SIDH 中的 Fp2）。其困难性假设是类群作用的可交换性：双方分别将秘密类群元素作用于同一条初始曲线，而可交换性确保双方最终得到同一条共享曲线。不公开任何辅助扭点信息，公钥仅是一个 j-不变量。这种设计经受住了针对 SIDH 的 Castryck-Decru 攻击。

在满足 p = 3 mod 4 的 Fp 上，超奇异曲线 E 具有一个特殊的自同态 pi（弗罗贝尼乌斯映射），其自同态代数包含虚二次序 Z[pi]。理想类群 Cl(Z[pi]) 在 Fp 上的超奇异曲线集合（按同构计）上自由且传递地作用。Cl(Z[pi]) 中的理想 a 作用于曲线 E，生成新曲线 a * E；这一过程可计算为曲线 E/E[a]，其中 E[a] 是与理想 a 对应的扭点子群。该作用具有可交换性：a * (b * E) = b * (a * E) = [ab] * E。这就是 CSIDH 的类群作用，为 Diffie-Hellman 提供了一个可交换版本。

CSIDH 密钥交换过程如下。公开参数：Fp 上的一条超奇异曲线 E0，以及较小的奇素数 l_1、...、l_n。秘密密钥：Alice 选择 a = (a_1、...、a_n)，其中每个 a_i 都属于 {-m、...、m}（随机的小整数）。Bob 选择 b = (b_1、...、b_n)。Alice 的公钥：E_A = [l_1^a_1 * ... * l_n^a_n] * E0。Bob 的公钥：E_B = [l_1^b_1 * ... * l_n^b_n] * E0。共享秘密：Alice 将自己的秘密指数作用于 E_B；Bob 将自己的秘密指数作用于 E_A。可交换性确保双方都得到 E_AB = [product(l_i^(a_i + b_i))] * E0。共享秘密是 j(E_AB)。不公开任何辅助点。

CSIDH 的参考实现使用 p = 4 * l_1 * l_2 * ... * l_74 - 1，其中 l_1 到 l_74 是前 74 个奇素数（3、5、7、...、373）。这使得 p 约为 512 位。每个秘密密钥分量 a_i 都属于 {-5、...、5}（每个分量有 11 种选择，共 74 个分量）。类群阶约为 sqrt(p)，密钥空间大小为 11^74。计算每一步同源映射时：对于每个素数 l_i，寻找 l_i-扭点子群，并使用 Velu 公式计算 l_i-同源映射。使用 sqrt-Velu 时，每一步大素数同源映射需要 O(sqrt(l_i)) 次运算。在现代硬件上，CSIDH-512 的完整密钥交换约需 1 到 5 毫秒。

原始 CSIDH 不是恒定时间的：Velu 步骤的数量取决于秘密密钥值 a_i，会通过时间侧信道泄露信息。CTIDH（恒定时间 ISOGENY Diffie-Hellman，Bernstein 等人于 2021 年提出）通过使用固定重量的密钥格式和经过精心设计的恒定时间同源映射计算解决了这一问题。CTIDH 秘密密钥被限制为绝对值之和固定的向量（例如，sum |a_i| = 130）。无论秘密密钥值如何，同源映射计算都以固定数量的步骤进行；当秘密指数为零时，使用虚拟同源映射计算来填充这些步骤。CTIDH 在严格的恒定时间保证下实现了与 CSIDH-512 相近的安全性，适用于嵌入式部署。

CSIDH 的量子安全性比基于格的方案更加复杂。已知最佳量子攻击使用 Kuperberg 在 2005 年提出的隐藏移位问题算法，以亚指数时间 L(1/2) = exp(O(sqrt(log p))) 破解类群作用结构。这明显优于经典攻击中最佳的 sqrt(p) 攻击，意味着与经典攻击者相比，量子计算机会显著削弱 CSIDH。若要达到 128 位后量子安全性（抵御 L(1/2) 攻击），CSIDH 需要约 5000 位的素数 p（CSIDH-5000）；而达到 128 位经典安全性只需 512 位。CSIDH-512 估计仅具备 62-72 位量子安全性，远低于 NIST Level 1 的要求。

CSIDH 的安全性依赖于群作用逆问题（GAIP）：给定 E_A = a * E0 和 E0，求 a。已知最佳算法是类似 Pohlig-Hellman 的归约与 baby-step-giant-step 相结合，经典运行复杂度为 O(sqrt(|Cl|)) ~ O(p^{1/4})。量子计算下的困难性（Kuperberg）使 CSIDH 的量子安全性低于基于 LWE 的方案。LWE 的最佳量子攻击（格筛法）提供了更加保守的安全裕度。CSIDH 的优势在于紧凑性：CSIDH-512 的公钥只有 64 字节（仅包含 j 不变量），而 ML-KEM-512 的公钥为 800 字节。对于要求密钥尽可能短、并且能够接受较低量子安全裕度的应用，CSIDH 仍然很有吸引力。

已有多个 CSIDH 变体，旨在应对其量子安全性方面的局限。BSIDH（B 表示“更好”）使用更高次数的基曲线以及椭圆曲线的乘积，在保持计算速度的同时增大类群规模。Csurf（曲面上的 CSIDH）使用另一组超奇异曲线，以实现更快的群作用计算。高亏格 CSIDH 方案使用 Fp 上亏格为 2 的曲线的雅可比，为群作用提供更大的空间，并可能带来更好的量子安全裕度。这些变体都尚未得到广泛采用或获得 NIST 考虑，部分原因是 CSIDH 变体的量子安全性分析仍在发展中，其成熟度不如基于格的方案。

CSIDH 和 SIDH 在基础设计上存在差异。可交换性：CSIDH 使用可交换的群作用（类群）；SIDH 则是使用带辅助挠点的非交换同源的非交互式密钥交换。基础域：CSIDH 在 Fp 上运行；SIDH 在 Fp2（二次扩域）上运行。公钥大小：CSIDH 为 64 字节（Fp 上的单个 j 不变量）；SIDH 为 324+ 字节（曲线加上两个 Fp2 点）。安全性：CSIDH 经受住了 Castryck-Decru 攻击；SIDH 已被攻破。量子安全性：CSIDH 要达到 128 位量子安全性需要 5000 位素数；在遭遇经典攻击之前，SIDH 具有相当的量子抗性。性能：CSIDH-512 约需 1-5 毫秒；SIDH 的性能与之相近，但 CSIDH-5000 会慢得多。

CSIDH 的可交换性支持非交互式密钥交换（NIKE）：Alice 发布 E_A = a * E0；Bob 发布 E_B = b * E0。之后无需任何进一步通信，任何人都可以利用任一公钥计算共享密钥：Alice 计算 a * E_B = a * (b * E0) = ab * E0；Bob 计算 b * E_A = b * (a * E0) = ab * E0。这种 NIKE 特性对于交互式密钥交换不切实际的应用很有价值——例如邮件加密，因为发件人和收件人不会同时在线。CSIDH 的 NIKE 类似于 Diffie-Hellman NIKE，但具备后量子特性。基于 LWE 的 ML-KEM 若不进行额外的协议设计，并不天然支持 NIKE。

CSIDH 尚未标准化，目前也没有部署到生产系统中。它是一个活跃的研究方向，已有多种实现：CTIDH（常数时间实现）、csidh-reference（用于教学的 Python 实现）以及 supersingular-isogeny-toolbox（经过优化的 C 实现）。部署的主要障碍是量子安全性：CSIDH-512 估计仅具备 62-72 位量子安全性，低于 NIST Level 1（128 位）的要求，因此不适合需要符合 NIST 标准的后量子应用。CSIDH-5000 可以达到安全要求，但速度会慢得多。研究人员仍在改进量子安全性分析，并研究能够缩小这一差距的变体；但截至 2024 年，CSIDH 仍是研究原型，而不是可直接部署的密码原语。

为什么 CSIDH 的可交换类群作用能够支持非交互式密钥交换？

CSIDH 使用 Cl(Z[pi]) 在 Fp 上的超奇异曲线上的可交换类群作用，其中 pi 是弗罗贝尼乌斯自同态。公钥是单个 j 不变量（64 字节）。它不发布辅助挠点，因此避免了 SIDH 的漏洞。类群作用具有可交换性，从而支持 NIKE。最佳经典攻击的复杂度为 O(p^{1/4})；最佳量子攻击（Kuperberg）以亚指数 L(1/2) 时间运行，因此要达到 128 位量子安全性需要 5000 位素数。CTIDH 提供常数时间实现。CSIDH-512 仅具备约 65 位量子安全性。CSIDH 尚未标准化；研究重点是在保持密钥紧凑的同时，通过变体提升量子抗性。