椭圆曲线同源的有效计算研究进展*

2021-05-23 06:12:22张方国
软件学报 2021年4期
关键词:利用优化

黄 艳 ,张方国

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]的签名方案……

登录APP查看全文

猜你喜欢
利用优化
利用min{a,b}的积分表示解决一类绝对值不等式
中等数学(2022年2期)2022-06-05 07:10:50
超限高层建筑结构设计与优化思考
房地产导刊(2022年5期)2022-06-01 06:20:14
民用建筑防烟排烟设计优化探讨
关于优化消防安全告知承诺的一些思考
一道优化题的几何解法
由“形”启“数”优化运算——以2021年解析几何高考题为例
利用一半进行移多补少
利用数的分解来思考
Roommate is necessary when far away from home
基于低碳物流的公路运输优化
现代企业(2015年2期)2015-02-28 18:45:09