椭圆曲线同源的有效计算研究进展*
2021-05-23张方国
黄 艳 ,张方国
1(中山大学 计算机学院,广东 广州 510006)
2(广东省信息安全技术重点实验室,广东 广州 510006)
椭圆曲线同源是两条椭圆曲线之间的一个非平凡的代数映射,它是一个群同态.根据Tate 定理[1],定义在有限域Fq上的两条椭圆曲线E1和E2同源当且仅当#E1(Fq)=#E2(Fq).然而,给定有限域上的两条椭圆曲线E1和E2,满足#E1(Fq)=#E2(Fq),找到E1与E2之间的同源是困难的.我们称该问题为标准的同源计算问题.
基于椭圆曲线同源的密码系统早期的研究主要集中在一般椭圆曲线(ordinary elliptic curve)上[2-4].根据Childs 等人[5]的研究结果,计算一般椭圆曲线同源的时间复杂度为量子亚指数时间;根据Biasse 等人[6]的研究结果,计算超奇异椭圆曲线(supersingular elliptic curve)同源的时间复杂度为量子指数时间.另外,Costello 等人[7]发现:在Montgomery 曲线上,超奇异椭圆曲线同源的计算比一般椭圆曲线同源的计算效率更高.
因此,从安全性和计算效率的角度来看,对于目前具有抗量子计算攻击的椭圆曲线同源的密码体制的研究主要集中在超奇异椭圆曲线同源上.Jao 等人[8]提出了扩域上的基于超奇异椭圆曲线同源的密钥交换协议(SIDH).之后,Azarderakhsh 等人[9]将基于SIDH 的加密方案和密钥封装协议提交到美国NIST,参与后量子密码方案的候选,并成功进入第2 轮.然而,其实现的效率相比于基于纠错码[10,11]和基于格[12,13],均不占优势.Yoo 等人[14]和Galbraith 等人[15]提出了基于超奇异椭圆曲线同源的签名方案,这两类签名方案均采用认证结构结合FS[16]转换或者U 转换[17]来加以构造,效率相比于基于格的[18,19]和基于哈希函数[20,21]的签名方案……
