M-SIDH和MD-SIDH：通过信息掩码对抗SIDH攻击

### M-SIDH和MD-SIDH：通过信息掩码对抗SIDH攻击 #### 1. 引言 1994年，Peter Shor描述了一种用于解决整数分解问题和离散对数问题的多项式量子算法。这意味着，在大规模量子计算机出现的情况下，我们如今广泛使用的加密协议将变得脆弱。为了减轻这一威胁，后量子密码学（有望在经典和量子计算机环境下都保持安全的加密协议）的研究在过去二十年中取得了显著进展。NIST PQC等标准化竞赛相继启动，目前已经提出了许多基于格、码、同源、多元方程组等问题的后量子难题候选方案。 同源是椭圆曲线之间的映射，在密码学应用中，我们主要关注定义在有限域$F_q$上的曲线。当存在同源$\varphi: E \to E'$时，我们称椭圆曲线$E$和$E'$是同源的，且连接两条同源椭圆曲线的同源有无数个。纯同源问题可表述为： - **问题1**：给定两条同源椭圆曲线$E$和$E'$，计算从$E$到$E'$的同源。 从曲线$E$到自身的同源称为$E$的自同态，$E$的所有自同态（包括零映射）构成的集合称为$E$的自同态环。在有限域上，椭圆曲线分为普通椭圆曲线和超奇异椭圆曲线两类。普通曲线的自同态环是二次虚数域中的一个序（因此是交换的），而超奇异曲线的自同态环是四元数代数中的一个极大序（因此是非交换的）。同源可以连接普通曲线之间以及超奇异曲线之间。 在普通/交换情况下，著名的Diffie - Hellman密钥交换协议可以直接应用于同源。像CRS、CSIDH、OSIDH等基于同源的方案就是这样实现的。其大致思路如下：有一个起始曲线$E_0$，Alice选择一个秘密同源$\varphi_A: E_0 \to E_A$，Bob选择一个秘密同源$\varphi_B: E_0 \to E_B$，双方交换$E_A$和$E_B$，然后各自从对方的公共曲线重新计算自己的秘密同源。由于同源是“可交换的”，他们最终会得到相同的终点曲线$E_{AB}$（同构意义下），其$j$ - 不变量被用作共享密钥。 然而，在使用超奇异曲线时，设计Diffie - Hellman类型的密钥交换并不那么直接，因为它们的自同态环是非交换的。2011年，Jao和De Feo提出了一个巧妙的想法，在超奇异情况下实现了一个交换图： 1. 固定同源$\varphi_A$和$\varphi_B$的度数$A$和$B$，且$A$和$B$互质； 2. Alice公开$E_0$的$B$ - 挠的一组基的像（即$E_0[B]$），Bob公开$E_0$的$A$ - 挠的一组基的像（即$E_0[A]$）。 这一想法催生了超奇异同源Diffie - Hellman协议（SIDH），该协议在过去十年中受到了广泛关注。基于SIDH的SIKE算法在2022年5月进入了NIST后量子标准化项目的第四轮。不过，在2022年8月，Castryck - Decru、Maino - Martindale和Robert提出的新攻击完全破解了SIDH和SIKE，使得SIKE算法在理论和实践上都不再安全。这些新攻击利用了SIDH协议中提供的挠点信息和同源度数信息，并且将同源问题嵌入到更高维度的同源问题中，从而影响了平衡参数。 鉴于SIKE和相关协议近年来受到的广泛关注，寻找应对这些新攻击的对策是很自然的。本文提出了两种对策：掩码度数SIDH（MD - SIDH）和掩码挠点SIDH（M - SIDH）。 #### 2. SIDH协议与攻击 ##### 2.1 SIDH协议 SIDH协议是一种类似Diffie - Hellman的密钥交换方案，它利用挠点信息来完成一个（伪）交换图： ```mermaid graph LR A[(E0, PA, QA, PB, QB)] --> B[(EA, φA(PB), φA(QB))] A --> C[(EB, φB(PA), φB(QA))] B --> D[EAB ∼= E ```