第 25 章基于同源的密码
25.1学习目标#
迄今为止讨论的家族——格、哈希和码——涵盖了 NIST 已标准化的全部方案，但它们并没有穷尽后量子密码的版图。标准分类法列出了五大家族 [1]，本章考察其中最年轻、数学上要求最高的一个：基于同源（isogeny-based）的密码，其困难性既不来自译码，也不来自短向量，而是来自在一张由椭圆曲线构成的巨大图中寻路。在所有后量子方法中，这一家族的密钥和签名最小；它也是催生了该领域最富戏剧性的警示故事的家族——一个旗舰方案进入了 NIST 竞赛的最后一轮，随后却在一个下午之内被彻底攻破。这两个事实都值得理解，而且它们是相互关联的。
本章是一篇综述，而不是实现指南。同源的数学博大精深，我们有意以严谨换取直观：目的是传达这些对象是什么、为什么其底层问题被认为是困难的、方案如何利用它，以及 2022 年的攻破摧毁了什么、又没有摧毁什么。
学完本章后，你应当能够：
回忆有限域上的椭圆曲线是什么，并将同源描述为两条此类曲线之间保持结构的映射；
解释什么使一条曲线成为超奇异曲线，并想象超奇异同源图的样貌，其快速混合性正是密码学困难性的来源；
陈述超奇异同源路径问题，解释为什么它对于经典计算机和量子计算机都被认为是困难的，以及为什么它带来了所有后量子家族中最小的参数；
将 SIDH/SIKE 描述为图上的 Diffie–Hellman 式密钥交换，并解释 Castryck–Decru 攻击如何利用该协议所泄露的辅助挠点信息，在多项式时间内恢复出其秘密钥；
定位在攻破之后幸存下来的方案——CSIDH 和 SQIsign——并解释为什么同源签名是已知最小的签名，尽管目前还没有任何同源方案成为 FIPS 标准。
本章为何重要。#
由多个后量子家族组成的投资组合的价值在于，它们会独立地失效：针对格的突破对码或同源毫无影响。基于同源的密码是这一组合中最极端的一点——带宽以巨大优势居于最小，建立在一个没有已知亚指数攻击的问题之上，但其所依托的数学工具只有区区二三十年的历史，所受的检验远少于格或码。SIDH 的故事是本书中对一个普遍原则最尖锐的例证：一个困难问题可能被悄然削弱，不是因为有人正面攻击它，而是因为协议白白交给了攻击者额外的信息。这一教训比给出它的方案更为长久。
25.2椭圆曲线与同源速成#
读者已经接触过有限域和多项式环，但还未接触过这一家族所依托的几何。本节只介绍够用的部分。一切都定义在有限域 \(\mathbb{F}_q\) 上，而对于密码学上有意义的情形，\(q = p^2\)，其中 \(p\) 是一个大素数。
椭圆曲线。#
椭圆曲线（elliptic curve）是一类特殊的三次方程，其解之间可以相互相加，从而将一个几何对象变成一个代数群。
定义 25.1 (有限域上的椭圆曲线). 设 \(\mathbb{F}_q\) 是特征大于 \(3\) 的有限域。\(\mathbb{F}_q\) 上的一条椭圆曲线 \(E\) 是方程 \[y^2 = x^3 + a x + b, \qquad a,b \in \mathbb{F}_q, \quad 4a^3 + 27b^2 \neq 0,\] 的解 \((x,y) \in \mathbb{F}_q \times \mathbb{F}_q\) 的集合，再加上一个特殊的无穷远点 \(\mathcal{O}\)。在几何的“弦切”加法律之下，这些点构成一个有限阿贝尔群，以 \(\mathcal{O}\) 为单位元。
关于这个群，有两个事实对我们很重要。第一，它的大小是有限的，并接近 \(q\)；经典的椭圆曲线密码（ECC）正是把秘密藏在这个群中，依赖于离散对数的困难性。而这种困难性恰恰是 Shor 算法所摧毁的，因此 ECC 不是后量子的。基于同源的密码沿用了这些曲线，却完全抛弃了离散对数，将秘密藏在 Shor 算法无法触及的地方：曲线之间的映射之中。
第二，每条曲线都带有一个数，即它的 \(j\) 不变量 \(j(E) \in \mathbb{F}_q\)，由 \(a\) 和 \(b\) 计算得出。两条曲线同构当且仅当它们的 \(j\) 不变量相等，因此我们可以把 \(j(E)\) 看作在重新标记意义下为曲线命名的指纹。本章中的方案传输的是 \(j\) 不变量，而不是方程。
同源。#
同源是从一条椭圆曲线到另一条椭圆曲线、同时保持几何结构和群结构的映射——它是这类对象上“态射”的自然概念。
定义 25.2 (同源). \(\mathbb{F}_q\) 上两条椭圆曲线之间的同源 \(\varphi : E_1 \to E_2\) 是一个非常值的有理映射，同时也是一个群同态，因此 \(\varphi(\mathcal{O}) = \mathcal{O}\) 且 \(\varphi(P + Q) = \varphi(P) + \varphi(Q)\)。它的核是被映到 \(\mathcal{O}\) 的点构成的有限子群，而（对于我们所使用的可分同源而言）它的次数就是这个核的大小。
关于同源，最有用的一个事实是它们由其核唯一确定。给定任意有限子群 \(G \subseteq E_1\)，存在一个核恰为 \(G\) 的同源 \(\varphi : E_1 \to E_2\)，它在目标曲线同构的意义下唯一，并且可以借助 Vélu 公式从 \(G\) 高效地计算出来。因此，“从 \(E_1\) 出发选择一个同源”与“选择 \(E_1\) 的一个有限子群”是同一回事。一个秘密同源实际上就是一个秘密子群，而沿一条长同源行走，就是复合许多小同源。
另有两个性质使同源表现得像一个连通良好的网络中的箭头。在复合之下次数相乘，因此一串次数为 \(\ell\) 的步骤构成一个次数为 \(\ell^e\) 的同源。并且，每个次数为 \(d\) 的同源 \(\varphi\) 都有一个反方向的、次数相同的对偶同源 \(\hat{\varphi}\)，满足 \(\hat{\varphi} \circ \varphi = [d]\)（乘以 \(d\)）。因此，固定小次数的同源总是成对出现，这使我们可以把它们看作一张图的无向边。
25.3超奇异同源图#
在 \(\mathbb{F}_{p^2}\) 上的所有椭圆曲线中，一类特殊且相对稀少的曲线——超奇异（supersingular）曲线——为密码学提供了舞台。其精确定义（一条其自映射环，即自同态环，异常庞大的曲线——它是四元数代数中的一个序，而不是虚二次域中的序）超出了综述的范围。重要的是它带来的后果。
一个小而紧密相连的世界。#
\(\mathbb{F}_{p^2}\) 上只有大约 \(p/12\) 个超奇异 \(j\) 不变量——这是一个有限集，但对于长达数百比特的密码学 \(p\) 而言，它是天文数字般庞大的。固定一个小素数 \(\ell\)（实践中取 \(\ell = 2\) 或 \(\ell = 3\)）。构造一张图：
顶点是 \(\mathbb{F}_{p^2}\) 上的超奇异曲线，每条曲线以其 \(j\) 不变量命名；
边是它们之间次数为 \(\ell\) 的同源；由于每个 \(\ell\) 同源都有一个次数为 \(\ell\) 的对偶，这些边是无向的。
每个顶点恰有 \(\ell + 1\) 个邻居，因此这张超奇异 \(\ell\) 同源图是 \((\ell+1)\) 正则的。它也是连通的：从任何一条超奇异曲线出发，都可以通过一系列 \(\ell\) 同源步骤到达任何另一条。
快速混合。#
使这张图在密码学上有用的性质在于，它是一个最优的扩展图（expander）——事实上是一个 Ramanujan 图，达到了正则图连通程度的理论极限。通俗地说，随机游走混合得极快：仅需大约 \(\log p\) 步之后，随机路径的终点就几乎均匀地分布在全部 \(\sim p/12\) 个顶点上，且不存在可检测的、偏向起点的偏差。因此，一条由数百个小步骤组成的秘密路径，会落在一条丝毫不透露所走路线的曲线上。这是同源版本的单向函数：向前复合这些步骤很廉价，但仅凭终点无法暴露路径。
25.4困难问题：寻找同源路径#
整个家族的安全性都建立在这样一个信念之上：游走无法倒着进行——只看到一条秘密路径的两个端点，并不能提供任何高效的方法来重构它。
定义 25.3 (超奇异同源路径问题). 给定 \(\mathbb{F}_{p^2}\) 上两条已知在 \(\ell\) 同源图中由一条路径相连的超奇异椭圆曲线 \(E_0\) 和 \(E_t\)，求一个同源 \(\varphi : E_0 \to E_t\)——等价地，求一串连接 \(E_0\) 与 \(E_t\) 的 \(\ell\) 同源步骤。
由于这张图是一个扩展图，两个端点看起来就像一对互不相关的曲线；\(E_t\) 的任何局部特征都不会指回 \(E_0\)。已知最好的经典算法是通用的寻路（中间相遇）搜索，其代价约为 \(\sqrt{p}\) 量级的工作量；而已知最好的量子算法——基于 Grover 式搜索的爪搜索（claw-finding）——代价约为 \(p^{1/4}\) 量级。两者在 \(p\) 的比特长度上都是完全指数级的：无论是经典的还是量子的，都没有已知的亚指数攻击，尤其不存在任何类似于 Shor 算法使大整数分解和离散对数崩塌的东西。这一问题与计算超奇异曲线自同态环的困难性密切相关，而后者被认为同样困难。
以极小的对象换取指数级的困难性，是这一家族最突出的优势。由于攻击的代价按 \(\sqrt{p}\) 或 \(p^{1/4}\) 增长，而不是对一个大型结构化密钥的温和削弱，因此几百比特的 \(p\) 就已足以换来充裕的安全余量。所传输的数据是 \(j\) 不变量和少量曲线坐标——几十到几百字节。在带宽方面，没有任何其他后量子家族能望其项背。问题在于（本章其余部分将展开讨论），一个协议可能不得不泄露比两个光秃秃的端点更多的信息，而危险就潜藏在这“更多”之中。
25.5SIDH 与 SIKE：图上的 Diffie–Hellman#
第一个实用的同源方案是 SIDH——超奇异同源 Diffie–Hellman（Supersingular Isogeny Diffie–Hellman）——由 Jao 和 De Feo 于 2011 年提出 [2]。它的形态与经典的 Diffie–Hellman 完全对应，由秘密同源扮演秘密指数的角色。
交换方块。#
固定 \(\mathbb{F}_{p^2}\) 上一条公开的起始曲线 \(E_0\)，其中 \(p\) 的选取使得 \(E_0\) 具有两种互素阶的丰富挠点——通常是 \(2\) 的幂和 \(3\) 的幂。双方在两张不同的图中游走：
Alice 选取一个阶为 \(2\) 的幂的秘密子群，并计算她的秘密同源 \(\varphi_A : E_0 \to E_A\)；
Bob 选取一个阶为 \(3\) 的幂的秘密子群，并计算他的秘密同源 \(\varphi_B : E_0 \to E_B\)。
双方各自公布自己游走的终点曲线（\(E_A\)、\(E_B\)）。如果此时每一方都能从对方的曲线出发重新应用自己的秘密同源，那么两条路线将会交换，并汇合于同一条共享曲线 \(E_{AB}\)，其 \(j\) 不变量即为共享秘密。这就是图 25.2 中的交换方块。
辅助挠点。#
微妙的要素就在这里。为了让 Bob 能从他的曲线出发重新应用 Alice 的同源，Alice 不仅必须公布 \(E_A\)，还必须公布 Bob 的挠子群的一组固定公开基在 \(\varphi_A\) 下的像——即 \(E_A\) 上的两个额外的点。Bob 也做对称的事情。正是这些辅助挠点像使每一方都能重构出对方的秘密子群平移到自己曲线上的结果，从而完成方块。它们对协议而言必不可少。它们也严格多于单纯的路径问题给予攻击者的信息：除了端点 \(E_0\) 和 \(E_A\) 之外，敌手还得到了秘密同源在一组已知点上的作用。
SIKE。#
用 Fujisaki–Okamoto 式变换（第 16.13 节）包装 SIDH，便得到 SIKE（超奇异同源密钥封装，Supersingular Isogeny Key Encapsulation），这是一个抗选择密文攻击的 KEM。SIKE 曾是 NIST 竞赛中一个有力的竞争者：它作为为数不多的剩余密钥封装候选方案之一进入了第四轮，最受推崇的是其格外小的密钥和密文——约为几百字节，比任何格或码的替代方案都小好几倍。十年间，它一直是“后量子安全只需多么少的带宽”的代表性范例。
25.62022 年的攻破#
2022 年夏天，SIDH 和 SIKE 被攻破。Castryck 和 Decru 给出了一种高效的密钥恢复攻击 [3]：给定一方的公钥，它能在多项式时间内重构出秘密同源。对于实际的 SIKE 参数，该攻击在一台普通计算机上只需运行几分钟到大约一小时——这不是安全级别的轻微削弱，而是彻底的崩塌。数周之内，其他研究者相继给出了独立的改进，对这一结果加以推广和加速。
攻击利用了什么。#
关键在于，这一攻击并没有求解超奇异同源路径问题。它针对的是 SIDH 所泄露的额外信息：辅助挠点像。其核心思想利用 Kani 的一个定理，将 Alice 的秘密同源与高维阿贝尔簇（椭圆曲线的乘积）之间的一个同源联系起来，而已知的挠点像恰好提供了逐步构造并计算这一高维对象所需的数据。每一步都检验并扩展一个关于秘密游走的猜测，而由于辅助点将游走约束得如此之紧，搜索便从指数级坍缩为多项式级。起始曲线的特殊结构——其自同态是已知的——使这一构造得以具体实现。
注 1.1. 这一区别值得尖锐地指出。上述定义中的抽象问题——从两条光秃秃的曲线中恢复一个同源——并未因这一攻击而被削弱，至今仍被认为是困难的。倒下的是 SIDH，因为 SIDH 交给攻击者的并不是两条光秃秃的曲线。它交给攻击者的是两条曲线外加一组已知挠基的像，而这些辅助信息足以完全绕开困难问题。困难性假设幸存了下来；方案使用它的方式却没有。
教训。#
这是本书中一个反复出现的隐患最尖锐的例子：协议主动提供的旁侧信息，可能在不触及困难问题本身的情况下将其削弱。SIDH 的设计者知道挠点像是额外的数据，但在十一年间无人看出如何将其化为武器；将它们转化为攻击的数学——高维同源——那时还根本没有与这一场景联系起来。这提醒我们，“底层问题是困难的”是方案安全的必要条件而非充分条件，而年轻的假设可能在很长时间内隐藏着这样的联系。
25.7幸存者：CSIDH 与 SQIsign#
这次攻破是专门针对 SIDH 的挠点构造的。那些不公布秘密同源在已知点上作用的同源方案未受影响，这一家族依然活跃。有两条路线值得一提。
CSIDH。#
CSIDH（“交换 SIDH”，读作“sea-side”）是一种建立在不同结构之上的密钥交换：理想类群在定义于素域 \(\mathbb{F}_p\) 上的一组超奇异曲线上的一个交换群作用。由于共享秘密纯粹是通过复合群作用元素而导出的，CSIDH 只传输曲线——没有辅助挠点像——因此 Castryck–Decru 攻击不适用于它。它的显著特点是，密钥交换是非交互的，并且像经典 Diffie–Hellman 那样具有交换性，而 SIDH 从未真正做到这一点。其代价在于，交换群作用容易受到一种亚指数量子攻击（Kuperberg 的隐藏平移算法）的威胁，因此 CSIDH 必须使用比具有指数级困难性的同类方案更大的参数，并且计算速度缓慢。它的确切安全级别仍有争议。
SQIsign。#
最突出的幸存者是 SQIsign（“短四元数与同源签名”，Short Quaternion and Isogeny Signature），由 De Feo、Kohel、Leroux、Petit 和 Wesolowski 于 2020 年提出 [4]。它是一个签名方案，建立在超奇异曲线与四元数序之间的对应关系（Deuring 对应）之上，依赖于自同态环/同源路径问题的困难性，而不依赖任何挠点技巧。它最突出的性质是尺寸：SQIsign 产生的签名和公钥以巨大优势在所有后量子签名方案中最小——签名约为两百字节，公钥只有几十字节，而格签名要一千字节甚至更多，基于哈希的签名则要许多千字节。代价是速度：签名和验证都远慢于格方案，历史上约为秒的量级，尽管后来的变体已将其大幅缩短。截至本书写作时，SQIsign 是 NIST 附加签名轮次（为格标准和哈希标准之外的签名而设的“入场通道”）中的候选方案，在那里，其极小的体积是主要吸引力，而其性能和年轻则是主要顾虑。
25.8权衡与现状#
基于同源的密码在设计空间中占据了一个清晰而不寻常的角落。
| 方案（NIST 级别 1） | 公钥 | 签名 | 家族 |
|---|---|---|---|
| SQIsign | \(\approx 64\) B | \(\approx 177\) B | 同源 |
| FN-DSA (Falcon-512) | \(897\) B | \(\approx 666\) B | 格 |
| ML-DSA-44 | \(1312\) B | \(2420\) B | 格 |
| SLH-DSA-128s | \(32\) B | \(7856\) B | 哈希 |
注 1.2. 同源这一押注是 Classic McEliece 的镜像。McEliece 以兆字节级的公钥为代价，换来四十年的保守稳健；同源则以年轻、速度以及已被证明的出人意料的能力为代价，换来所有家族中最小的带宽。SIKE 的攻破并不是抛弃这一家族的理由——它从未解决的路径问题依然屹立——但它是一个长久的警示：这里的假设只经受了数年而非数十年的检验，地基仍有可能发生移动。
现状。#
没有任何基于同源的方案是 FIPS 标准。SIKE 曾是 NIST 第四轮的 KEM 候选方案，在 2022 年被攻破后已退出。截至本书写作时，SQIsign 正在附加签名轮次中接受评估，因其无与伦比的紧凑性而受到重视，但受限于性能及其安全基础相对年轻；它能否进入标准化尚无定论。CSIDH 仍是一个参数存在争议的研究级方案。如实的总结是：基于同源的密码是最有前景的小体积后量子家族，同时也是最不成熟的——它是一个活跃的研究领域，而非一套成熟的工具箱。
25.9常见陷阱#
陷阱 1：认为底层问题困难就能使方案安全。#
这就是 SIKE 的教训，也是本章最重要的思想。超奇异同源路径问题从未被攻破；SIDH 之所以被攻破，是因为它泄露的信息多于该问题——即已知挠点在秘密同源下的像——而这些多出来的信息已经足够。安全性证明的强度仅取决于它实际归约到的那个假设，而一个泄露辅助结构的协议，可能归约到的是一个比其设计者预想的容易得多的问题。
陷阱 2：把“密钥最小”当作“最好”。#
同源方案在带宽上占有决定性优势，人们很容易把这当作总体评判。但并非如此。它们速度慢，假设年轻，并且已经有一个旗舰方案倒下。尺寸只是若干维度之一；保守性和速度则指向另一个方向，对大多数部署而言，格方案的均衡性仍是今天更安全的默认选择。
陷阱 3：以为 2022 年的攻破葬送了整个家族。#
Castryck–Decru 攻击专门针对 SIDH 和 SIKE 的挠点构造。不公布此类像的方案——CSIDH、SQIsign——不受其影响，而这一家族通过 SQIsign 仍是一个活跃的标准化候选者。“SIDH 已被攻破”与“同源已被攻破”是截然不同的两个陈述；只有前者为真。
陷阱 4：忘记这个领域有多年轻。#
格和码已经被攻击了数十年；超奇异同源假设接受集中密码分析的时间则短得多，而其中涉及的数学——自同态环、高维同源、Deuring 对应——足够深奥，足以隐藏更多的联系。年轻并不是缺陷，但它是要求采用混合部署、避免仅凭同源保护长期秘密的理由。
25.10小结#
基于同源的密码是后量子家族中的第五个，也是最年轻的一个，并且是与本书其余部分相去最远的一个：
它的对象是有限域上的椭圆曲线以及它们之间的同源——保持结构的映射——这些同源被组织成一张超奇异同源图，它是一个快速混合的扩展图；
它的困难问题是超奇异同源路径问题——从两条端点曲线中恢复一条秘密路径——无论经典还是量子，都没有已知的亚指数攻击，因此带来了所有家族中最小的密钥和签名；
SIDH/SIKE [2] 将其转化为 Diffie–Hellman 式的密钥交换，进入了 NIST 第四轮，随后于 2022 年在多项式时间内被攻破 [3]——不是通过求解路径问题，而是通过利用协议所泄露的辅助挠点像；
幸存者——用于密钥交换的 CSIDH 和提供已知最小签名的 SQIsign [4]——避免了这种泄露，而 SQIsign 是 NIST 附加签名轮次中的活跃候选方案，尽管目前尚无任何同源方案成为 FIPS 标准。
SIDH 攻破的教训并不是同源失败了——其核心假设依然完好——而是一个困难问题可能被协议围绕它所公布的信息所削弱。结合这一家族的紧凑性及其相对的年轻，这使基于同源的密码处于后量子投资组合中高风险、高回报的一端：可用的最小体积，建立在最不稳固的地基之上。
评论