SIDH 中3e3 -挠基的快速生成*

王 颖 李梦东 朱屹霖

北京电子科技学院，北京市 100070

引言

同源密码是一种新型的后量子密码形式，其基本方案是SIDH(Supersingular Isogeny Diffie-Hellman)密钥交换协议[1]。 同源密码具有高安全性和公钥长度较小的优点，根据SIDH 的改进而成的SIKE 算法，已经成为NIST 后量子密码征集活动第三轮的备用算法之一。 但相对于其他后量子密码类型，SIDH 也有相对较长的计算时间的缺点，如何提升SIDH 实现效率是需要加以解决的问题。

在SIDH 密钥交换协议中公钥生成和传输方面，最初的公钥是使用(E，xP，xQ) 形式的三元组完成的[2]，其中E:y2=x3+ax+b，xP，xQ是P 和Q 的横坐标。 因此，公钥的传输实质上是使用四个元素a，b，xP，xQ∈Fp2，需要8log p比特。

文献[3] 等人提出形如PK= [xφ(P)，xφ(Q)，xφ(Q-P)]∈F3p2的公钥表示，将其大小减小为6log p比特，这也方便在解压缩过程中使用三点阶梯函数[4]，使计算效率更高。

文献[5]提出SIDH 公钥压缩的思路，将公钥中的点展开为挠基的线性组合，只传递其中的系数可进一步实行公钥长度的缩短。 首先用j不变量来表示曲线E， 它也是Fp2的一个元素，同源类是由j不变量唯一决定的。 其次用ℤt⊕ℤt中的元素来表示点P、Q，将公钥表示减小到4log p比特。 然而，这种公钥尺寸的减少也带来了相当高的计算开销。

文献[6]等人进一步压缩点P、Q 的表示，将公钥大小减少到3.5log p比特，并在挠基的生成阶段采用2-下降算法进行提速。 文献[7]等人提出纠缠基和反向基分解的概念，很大程度上减少了SIDH 压缩和解压缩的运行时间。 文献[8]等人对公钥压缩技术进一步的研究，降低了生成2e2-挠基的复杂度，对生成3e3-挠基的解压过程也提出了改进。 文献[9]等人提出对偶同源，对生成3e3-挠基和配对过程进行了结合，提高了整体实现效率。

本文详细分析和描述了之前学者提出的关于生成3e3-挠基的实现步骤，并进行补充。 同时提出了新的改进方法，使得生成挠基时在随机点的阶为2r的情况下，减少e2-r次点2 倍计算，从而提高整体生成基的效率。

1 预备知识

1.1 SIDH 密钥交换协议

超奇异同源Diffie-Hellman(SIDH)密钥交换算法是依赖同源问题的Diffie-Hellman 算法，不受量子攻击的影响[10]，文献[2]中也证明了:在SSDDH(Supersingular Decision Diffie-Hellman)假设下，SIDH 密钥协商协议在Canetti 和Krawczyk[11]的认证链路对抗模型中具有会话密钥安全性。

SIDH 协议双方需要交换他们的公开密钥，每个公开密钥由椭圆曲线E′和E′上的两点P，Q 组成[12]。 设有限域Fp2上定义一个形式为p=lelmem ±1 的大素数，其中l和m都是小素数且lel≈mem，l和m通常分别等于2 和3。 选择一个超奇异椭圆曲线E， 满足＃EA(Fp2)= (lelmem)2。SIDH 密钥交换过程可以概括为以下步骤:

①Alice 和Bob 分别在公共椭圆曲线E/Fp2上产生两个独立点PA，QA和PB，QB；

②Alice 通过两个阶为lel的独立点生成E的挠子群E[lel]=PA，QA，群中元素阶为lel；Bob通过两个阶为mem的独立点生成E的挠子群E[mem]=PB，QB，群中元素阶为mem；

③Alice 随机选取秘密整数sA和tA∈ℤ /lelℤ ，且两者都不能被l整除，生成点RA=[sA]PA+ [tA]QA，RA的阶为lel；Bob 随机选取秘密整数sB和tB∈ℤ /memℤ ，且两者都不能被m整除，生成点RB= [sB]PB+ [tB]QB，RB的阶为mem；

④Alice 得到RA生成的循环群RA，＃RA=lel；Bob 得到RB生成的循环群RB，＃RB=mem；

⑤Alice 根据核KerφA=RA，得到同源φA:E→EA(唯一)[13]，作为Alice 的私钥，这里EA=E/RA； Bob 根据核KerφB=RB，得到同源φB:E→EB(唯一)[13]，作为Bob 的私钥，这里EB=E/RB；

⑥ Alice 将φA(PB)、φA(QB)、EA发送给Bob；Bob 将φB(PA)、φB(QA)、EB发给Alice，这些是双方的公开信息；

⑦Alice 和Bob 通过计算得到的EAB=EBA=E/RA，RB，可以作为对称加密的共享秘钥。

1.2 SIDH 公钥压缩

SIDH 的公钥压缩是指将传输的公钥以更小比特的形式表示出来，文献[6]将公钥大小压缩到了3.5log p比特，但是其压缩过程所用的计算成本仍然较高。

以Alice 端为例，定义在Fp2上的椭圆曲线E和E/RA，挠子群E[lel] 的生成点PA和QA， 点φA(PB) 和φA(QB) 作为她公开参数。

公钥压缩(解压缩)过程可以概括为以下步骤:

①生成挠基:压缩时Alice 生成挠子群E/RA[lel] 的二维挠基{R1，R2}∈Fp2[lel]；解压缩时Bob 按照顺序生成相同的挠基{R1，R2}；

1.3 Elligator 2 生成随机点

2 已有3e3 -挠基生成的算法分析

2.1 naïve 算法

2.2 3-下降算法

2.3 算法分析

生成2e2-挠基的过程通过纠缠基技术在实现效率上得到了很大的提升，但是由于很难应用到3e3的情况下，现有的方法仍然需要分别生成不相关挠点。

下降算法减少了在判断阶数时使用余因子乘法的频率，但是在寻找3 阶点P3时，也需要大量的余因子乘法来判断阶数。

Zanon 等人[7]通过实验观察到，l= 2 时，naïve 方法总是比3-下降算法快。 但两者都需要大量的余因子乘来判断阶数，计算成本较高。本文对此进行了优化，具体描述在下一节给出。

3 改进后的SIDH 的3e3 -挠基生成

为了降低余因子乘的次数，本文在已有的挠基生成技术基础上，对随机点的阶数是否为2r进行判断，在生成3e3-挠基的情况下，减少e2-r次点2 倍计算。 因为naïve 算法和3-下降算法都需要余因子乘来判断阶数，所以本文的这项优化分别应用在两种算法上，同时提高生成基效率。

3.1 在naïve 方法中的改进

3.2 在3-下降方法中的改进

在3-下降方法中，寻找3-挠点P3时也通过乘余因子的方法来判断阶数。 所以同样在计算点2 倍算法时添加判断，若出现Z=0 的情况，就舍弃，立即进入下一轮的迭代来减少不必要的成本本支出。

针对3-下降算法改进如下:

3.3 点2 倍算法改进

无论是naïve 算法还是3-下降算法，都应用了最基础的点2 倍算法，所以本文提出的改进是在点2 倍算法中实现的。 在SIKE 说明文件[17]中点2 倍算法也就是用Double 函数来完成的。根据本文的改进，在循环的最后一步添加了判断，如果得到了可以使z= 0 的点，就立即终止计算，主函数就要重新生成随机点。

改进后的算法1 如下:

算法1 在Montgomery 曲线E/Fp2:y2 = x3 +Ax2 +x 上计算r次点2 倍后的x 坐标输入:曲线系数A24 = (A + 2)/4，点(x，z) 和整数r。输出:点(x’，z’) = [2r](x，z) ∈E。1for j = 1 to r do 2a ←x + z；3b ←x - z；4 aa ←a2；5bb ←b2；6c ←aa - bb；7x ←aa·bb；8 z ←c(bb + A24·c)；9 if z = 0 then 10 Abort； / /说明生成点的阶为2i 11return x，z；

4 改进算法效果分析

4.1 在naïve 算法中的改进效果分析

表1 列出了优化方案的成本对比。

表1 减少成本对比

4.2 在3-下降算法中的改进效果分析

在3-下降算法中确定一个非平凡3-挠点P3仍然是一个需要乘余因子的高消耗过程，本文观察到，在寻找3-挠点P3时，同样没有考虑Elligator 2 的生成点阶数为2r(1＜r≤e2)的可能性，当生成点R∈[3e3]E时，无法得到阶为3的点或者是阶为3e3的点，所以立即重新生成随机点可以省去e2-r次点2 倍的计算。

5 结论

在SIDH 公钥压缩生成3e3-挠基的这一步中，已有的naïve 和3-下降算法都无法避免大量的余因子乘法，而余因子乘法所用成本又相对较高，所以本文通过在点2 倍乘法的过程中判断随机点阶数是否为2r，来排除[3e3]E中的点，从而加快生成正确阶数挠点的速度。

提高SIDH 公钥压缩计算速度的是一项十分有意义的工作，本文只针对生成随机点阶数为2r(1＜r≤e2)的情况进行了优化，其他情况下仍然需要高成本的计算，所以仍然有进一步研究的必要。