同源密码方案综述.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(4):667684密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]同源密码方案综述*刘一丹,程庆丰信息工程大学 网络空间安全学院,郑州 450001通信作者:程庆丰,E-mail:摘要:基于超奇异椭圆曲线同源构造的密码体制作为后量子密码的重要分支,因其较小的密钥尺寸和良好的抗量子特性,成为一个很有潜力的发展方向.本文对同源密码进行了简要概述,总结同源密码底层的数学困难问题;整理了近年来基于椭圆曲线同源构造的不同密码方案,分别从两方密钥交换、组密钥交换、数字签名、不经意传输和公钥加密等方面介绍国内外同源密码发展现状;总结了该领域一些需要重点解决的问题,对同源密码未来发展前景进行展望.关键词:同源密码;后量子密码;超奇异同源 Diffie-Hellman中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000626中文引用格式:刘一丹,程庆丰.同源密码方案综述J.密码学报,2023,10(4):667684.DOI:10.13868/ki.jcr.000626英文引用格式:LIU Y D,CHENG Q F.A survey of isogeny-based cryptographic schemesJ.Journal ofCryptologic Research,2023,10(4):667684.DOI:10.13868/ki.jcr.000626A Survey of Isogeny-Based Cryptographic SchemesLIU Yi-Dan,CHENG Qing-FengSchool of Cyber Science and Technology,Information Engineering University,Zhengzhou 450001,ChinaCorresponding author:CHENG Qing-Feng,E-mail:Abstract:Cryptosystems based on supersingular elliptic curve isogenies is a class of the mostimportant post-quantum cryptosystems.Due to their small key size and good post-quantum properties,isogeny-based cryptosystems have become promising candidates in PQC standardization.This papergives a brief overview of isogeny-based cryptosystems and summarizes the underlying mathematicalproblems.This paper also classifies recent isogeny-based cryptographic schemes,surveys the currentresearch results,and traces their development in detail following their categories such as two-partykey exchange,group key exchange,digital signature,oblivious transfer and public key encryption.Finally,some important problems that need to be solved in this field are summarized,and the futuredevelopment prospect is discussed.Key words:isogeny-based cryptography;post-quantum cryptography;supersingular isogeny Diffie-Hellman*基金项目:国家自然科学基金(61872449,62172433)Foundation:National Natural Science Foundation of China(61872449,62172433)收稿日期:2022-08-01定稿日期:2022-09-26668Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.20231引言现代公钥密码学体制大多数依赖于特定数学问题的困难性,例如大整数分解和离散对数问题等.Shor1于 1994 年提出一种高效求解大整数分解问题和离散对数问题的量子算法,而随着目前实用可扩展量子计算机研发不断深入,量子计算开始给传统公钥密码体制的安全性带来严重威胁,寻找能够抵抗量子计算攻击的公钥密码体制迫在眉睫.基于超奇异椭圆曲线同源构造的密码体制作为后量子密码的重要分支之一,成为一个新兴并十分有发展前景的方向.椭圆曲线在密码学中应用的发展历史可以简要分为以下三个阶段:第一阶段,1985 年 Koblitz 和Miller 分别独立将椭圆曲线引入密码学,该阶段主要应用基于离散对数的椭圆曲线;第二阶段,2000 年Joux 引入基于配对的椭圆曲线,将椭圆曲线上的离散对数问题转化为有限域上的离散对数问题;第三阶段,2006 年 Rostovtsev 和 Stolbunov2利用椭圆曲线同源关系构造密码学方案,并在此基础上构造后量子密码方案.椭圆曲线同源本质上是两条椭圆曲线之间的非零有理映射,该映射保持运算且将无穷远点映射为无穷远点,简而言之,同源是能保持椭圆曲线结构的一个映射.基于椭圆曲线同源的密码学方案的安全性依赖于有限域上寻找椭圆曲线间同源的假设困难性,基于该数学难题可以构造一系列后量子密码方案.最早的基于椭圆曲线同源的后量子密码方案要追溯到 1996 年,Couveignes 在巴黎师范学院的一个研讨会上提出基于一般椭圆曲线同源映射来构造密钥交换,但相关论文没有正式发表.直到 2006 年,Rostovtsev和 Stolbunov2利用一般椭圆曲线之间的同源关系进行方案的构造,提出一般椭圆曲线同源密钥交换(ordinary isogeny Diffie-Hellman,OIDH)协议,该方案实现效率较低,但具有非交互的性质且形式简单.然而,由于一般椭圆曲线同源的群作用是交换的,Childs 等3提出一个亚指数时间的量子算法解决了这个一般椭圆曲线同源问题.因此,研究人员考虑使用超奇异椭圆曲线之间的同源来构造密码方案.2011 年,Jao 和 De Feo4利用超奇异椭圆曲线构造了 SIDH(supersingular isogeny Diffie-Hellman)方案,该方案基于寻找超奇异椭圆曲线间同源关系的假设困难性构造,比 OIDH 方案快,然而该方案已于 2022 年被完全攻破5.经过多年的研究,基于椭圆曲线同源的密码体制已有很多成果,现如今的同源密码大致可以分为两方密钥交换、组密钥交换、数字签名、不经意传输和公钥加密等几类密码体制,如图1所示.图 1 同源密码方案概况Figure 1 Overview of isogeny-based cryptography schemes本文其他各部分内容安排如下:第2节主要介绍同源密码的预备知识;第3节对近年来基于椭圆曲线同源构造的密码方案进行综述,分别从基于同源的两方密钥交换、组密钥交换、数字签名、不经意传输和公钥加密等角度梳理当前研究成果,归纳了几类密码体制的发展现状;第4节根据现有的研究情况,总结了该领域一些需要重点解决的问题,并对未来发展前景进行了展望;最后,第5节总结论文.刘一丹 等:同源密码方案综述6692预备知识本节重点介绍同源定义和同源密码方案涉及的困难问题.具体细节可以参看文献 4.2.1同源曲线定义 1(同源)如果定义在域 K 上的椭圆曲线 E1和 E2之间存在有理映射:E1 E2,(x1,y1)7(x2,y2),O O,其中 O 是无穷远点,把 E1的无穷远点映射为 E2的无穷远点,且 是同态,那么称 是同源映射,E2是 E1的同源曲线.2.2困难问题定义 2(超奇异同源问题(supersingular isogeny problem,SSI)给定有限域 K 和定义在域 K 上的两个超奇异椭圆曲线 E1和 E2,使得|E1|=|E2|,计算同源 :E1 E2.定义 3(超奇异计算性 Diffie-Hellman 问题(supersingular computational Diffie-Hellman problem,SSCDH)A:E0 EA是核为 GA=m1P1+n1Q1 的同源,其中 m1,n1 Z/le11Z 且不同时整除 l1.B:E0 EB是核为 GB=m2P2+n2Q2 的同源,其中 m2,n2 Z/le22Z 且不同时整除l2.给定(E0,P1,Q1,P2,Q2;EA,A(P2),A(Q2);EB,B(P1),B(Q1),SSCDH 问题的目标是找到E0/GA,GB 的 j 不变量.定义 4(超奇异判定性 Diffie-Hellman 问题(supersingular decision Diffie-Hellman problem,SS-DDH)给定以 1/2 概率采样的两种分布如下,确定元组从哪个分布中进行采样.(EA,EB,A(P2),A(Q2),B(P1),B(Q1),EAB),其中 EA,EB,A(P2),A(Q2),B(P1),B(Q1)和定义3中的相同,且 EAB=E0/m1P1+n1Q1,m2P2+n2Q2;(EA,EB,A(P2),A(Q2),B(P1),B(Q1),EC),其中 EA,EB,A(P2),A(Q2),B(P1),B(Q1)和定义3中的相同,且EC=E0/m1P1+n1Q1,m2P2+n2Q2,其中m1,n1(m2,n2)从 Z/le11Z(Z/le2eZ)中随机选择且不能同时被 l1(l2)整除.定义 5(带哈希的超奇异判定性 Diffie-Hellman 问题(hashed SSDDH problem)给定(E0,P1,Q1,P2,Q2;EA,A(P2),A(Q2);EB,B(P1),B(Q1);h),令 H:0,1 0,1是哈希函数、A:E0 EA是核为 GA=P1+aQ1 的同源(a Z/le11Z)、B:E0 EB是核为 GB=P2+bQ2的同源(b Z/le22Z)、EAB=E0/.以 1/2 的概率计算 h=H(j(EAB)或 h 0,1,判定 h 是以哪种方式计算的.定义 6(1-gap SIDH 问题)给定(E0,P1,Q1,P2,Q2;EA,A(P2),A(Q2);EB,B(P1),B(Q1);h)和一个有限预言机 OB.令 H:0,1 0,1是哈希函数、A:E0 EA是核为 GA=P1+aQ1 的同源(a Z/le11Z)、B:E0 EB是核为 GB=P2+bQ2 的同源(b Z/le22Z),找到 E0/GA,GB 的 j 不变量.3同源密码方案研究现状基于椭圆曲线同源构造的主流密码方案主要可以分为两方密钥交换、组密钥交换、数字签名、不经意传输和公钥加密等几类密码体制,本节主要对其进行分类整理,综述研究现状.3.1两方密钥交换协议由第2节可以看出,椭圆曲线同源相关困难问题与离散对数问题及其变体类似,双方交换一对由私钥生成的公钥,并将其组合成一个共享密钥.不同的是,SIDH 方案依赖于涉及超奇异椭圆曲线同源的新的计算假设族,取代了传统的离散对数问题和计算和判定性 Diffie-Hellman 问题,其中 SSCDH 问题对应于CDH 问题、SSDDH 问题对应于 DDH 问题、SIDH 协议对应于传统的 DH 协议等.虽然 SIDH 目前已被完全攻破,但其他同源密码方案的安全性还有待进一步研究.670Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023基于椭圆曲线同源的两方密钥交换协议的基本工作原理如下:A 秘密随机选取两个元素 m1,n1Z/le11Z,它们不能都被 l1整除,然后计算同源 1:E0E1,其中核为 m1P1+n1Q1,E1=E0/m1P1+n1Q1,A 的公钥为 E1,1(P2),1(Q2).类似地,B 秘密随机选取两个元素m2,n2 Z/le22Z,它们不能都被 l2整除,然后计算同源 2:E0 E2,其中核为 m2P2+n2Q2,E2=E0/m2P2+n2Q2,B 的公钥为 E2,2(P1),2(Q1).之后,A 计算同源映射 3:E2 E21,其中核为 m12(P1)+n12(Q1).B 计算同源映射 4:E1 E12,其中核为m21(P2)+n21(Q2).可以证明,E12和 E21是同构的,因此二者具有相同的 j 不变量作为 A和 B 的共享密钥.学者们基于该原理设计出一系列安全性较高的不同模型下的基于椭圆曲线同源的密钥交换协议,具体方案如下.2011 年,Jao 和 De Feo4提出 SIDH 方案,该方案基于寻找超奇异椭圆曲线间同源关系的假设困难性构造.与 OIDH 方案相比,SIDH 方案执行速率更高,耗时更短.遗憾的是,SIDH 方案的安全性方面存在较大的不足.首先,SIDH 方案类似传统的 DH 方案,没有实现认证功能,这使得 SIDH 方案不能抵抗中间人攻击.其次,Castryck 等5在 2022 年对该方案提出了一种高效的密钥恢复攻击.2018 年亚密会上,Castryck 等6将超奇异椭圆曲线与 OIDH 方案结合,提出一种后量子安全的非交互式密钥交换方案CSIDH(commutative supersingular isogeny Diffie-Hellman)方案.该方案允许以非常低的成本进行公钥验证,实践中运行速度很快,安全强度与 AES-128 相当.同年,Galbraith 等7研究了实现基于超奇异同源 Diffie-Hellman 的认证密钥交换(authenticated key exchange,AKE)的不同方法,提出了 SIDH-AKE协议并在 CK 模型下证明了该方案的安全性.徐秀等8基于孪生 Diffie-Hellman 问题提出了一种超奇异同源 MQV-型两轮 AKE 协议,并在 CK 模型下证明了该方案的安全性.该方案通过压缩扭点的方式减小带宽,相比格上的其它方案密钥长度较短,但计算量更大.另外,Fujioka 等9也基于超奇异同源提出两个 AKE 协议,其中一个基于判定性 Diffie-Hellman 假设在量子随机预言模型(quantum random oraclemodel,QROM)下是可证安全的,另一个基于 gap Diffie-Hellman 假设是可证安全的.此外,LeGrow等10基于 CK 模型提出第一个允许量子叠加查询的认证密钥建立模型,允许敌手和量子预言机之间进行量子交互,给出在该模型下设计安全协议的一般构造方法,并在此基础上构造了一个基于同源的认证密钥建立协议.而 Taraskin 等11则提出了第一个基于超奇异椭圆曲线同源的抗量子口令认证密钥交换(password-based authenticated key exchange,PAKE)方案 TSJL,并基于 SI-APC(supersingularisogeny auxillary point computation)假设讨论了该方案在 BPR(Bellare-Pointcheval-Rogaway)模型中的安全性.2019 年,Flynn 等12研究了主极化超奇异阿贝尔曲面(principally polarised supersingular Abeliansurfaces,PPSSAS)的同源图,并提出了一个亏格 2 的 SIDH 变体(genus-2 variant of the SIDH,G2SIDH),该方案在相同安全级别下所用素数尺寸更小,但需要进一步改进算法以获得更高效的实现.同年,Soukharev 等13提出一个基于椭圆曲线同源的密钥协商方案 PQDH(post quantum Diffie-Hellman),该方案不需要区分发起者和响应者,并在此基础上构造了一个 PAKE 方案,安全性与 Taraskin等11的方案几乎相同.此外,Terada 等14将 SIDH 与 EKE(encrypted key exchange)结合提出新的PAKE 方案 SIDH-EKE 和 CSIDH-EKE,该方案基于标准假设在随机预言模型和理想密码模型下是可证明安全的,计算成本和通信成本几乎与 SIDH 相同,比 Taraskin 等人11的方案实现了更紧凑的通信开销.Xu 等15首先提出了一个基于 1-Oracle SSI 假设的三次交互 AKE 方案,为了提高可靠性,又提出了一个基于标准 SSI 假设的两次交互 AKE 方案,并证明了这两个方案在 CK+模型中的安全性.2020 年,Col 等16引入一类 O-定向超奇异椭圆曲线(O-oriented supersingular elliptic curves),基于超奇异椭圆曲线子集上的虚二次阶理想类群的作用,提出了一个定向超奇异同源 Diffie-Hellman(ori-ented supersingular isogeny Diffie-Hellman,OSIDH)协议,该方案可以看作 CSIDH 的推广,通过交换类群在公共曲线的邻域中作用的部分信息来实现密钥交换,避免了一些影响安全性的不利因素.同年,Vzquez 等17提出 eSIDH(extended SIDH),运行速度更快,可以并行化实现,尤其是在多核平台上运行时产生了显著的加速因子,效率更高.De Kock 等18基于 CSIDH 构建了一个抗量子的 AKE 算法,在强 CSIDH(strong CSIDH)假设下,实现了首个具有弱前向安全的隐式认证的类 CSIDH 协议,与之前基于椭圆曲线同源的 AKE 协议相比,该方案简单且具有最优的通信复杂度,安全证明具有最优的紧密性,刘一丹 等:同源密码方案综述671但在量子随机预言模型下证明安全性还有待研究.此外,Kawashima 等19证明了 CSIDH 的计算问题和gap 问题是随机自约化的,并基于 CSIDH 提出了一种高效的 AKE 方案,具有较小的安全损失,在 110比特安全级别下,证明了该方案在已有 CSIDH 类方案中是最快的.另外,Kunzweiler 等20对 G2SIDH的密钥空间进行深入的分析,提出了多项式时间的自适应攻击,能够在配备有返回单比特信息的预言机时恢复密钥.Costello 等21提出了一种实例化基于同源的密码方案的新方式,相比相同安全级别的 SIKE,B-SIDH 采用了更小的素数.2021 年,Dobson 等22为信号 X3DH 密钥交换协议提出了一个基于 SIDH 的替代方案 SI-X3DH协议,该协议实现了可否认性并具有较好的效率,满足信号 X3DH 协议的所有安全属性,基于 HCDH(honest computational Diffie-Hellman)假设和 VCDH(verifiable computational Diffie-Hellman)假设在 signal-adapted-CK 模型中是可证明安全的.同年,Fouotsa 等23还提出了一种直接对抗 GPST 自适应攻击的新方法,并利用该方法设计了一个高效的交互式 SIDH 型静态-静态密钥交换协议 HealSIDH(healed SIDH).另外,Onuki 等24重新审视了 OSIDH 的理论背景,给出了 OSIDH 的一个定理证明.2022 年,Qi 等25将 SIDH 和 SIKE(supersingular isogeny key encapsulation)作为构建模块,提出了一个基于超奇异同源的后量子 AKE 协议,并在强 eCK 和 CK+安全模型下证明了该协议的安全性.此外,该协议中相对耗时的封装算法可以提前离线执行,相比其它 AKE 协议获得效率优势.同年,Dartois等26基于 Onuki 的工作,针对 OSIDH 提出一种新的攻击,证明了 OSIDH 中水平同源链传递的附加信息可以用来恢复密钥,但该攻击具有指数级的复杂性.此外,Kutas 等27讨论了针对 SIDH 类型密码系统的扭点攻击.Castryck 等5针对 SIDH 提出了一个高效的密钥恢复攻击,并用 Magma 实现一个单核运行,大约一个小时就打破了 SIKEp434 的实例.Maino 等28提出了一种不需要起始曲线上任何自同态信息就可以攻击 SIDH 的方法,在合理时间内解决了 SSI-T(supersingular isogeny with torsion)问题,该攻击具有亚指数时间复杂度,因此显著降低了 SIDH 和 SIKE 的安全性,该攻击适用于 Sta 和B-SIDH 等密码系统,但不适用于 CSIDH、CSI-FiSh(commutative supersingular isogeny based Fiat-Shamir signatures)和 SQISign(short quaternion and isogeny signature)等密码系统.Robert 等29提出了一个在多项式时间内攻破 SIDH 的方法,该方法即使在随机起始曲线下也能实现,在 8 维情况下有可能在多项式时间内攻破 SIDH 的所有参数.由于以上这些攻击方法,SIDH 和 SIKE 类方案已不安全.经过十多年的研究,除了上述介绍的一些基于椭圆曲线同源的两方密钥交换协议外,还有其他一些相关的研究成果,表1中汇总了当前已有的一些两方密钥交换协议优秀成果.3.2组密钥交换协议在如今的环境中,在线服务常常需要多个参与方同时进行交互.在利用一般椭圆曲线构造组密钥交换协议时,对于 n 方可以使用 n 1 轮密钥交换,该方法较为简单,可以直接推广到基于同源的组密钥交换协议中.但该方法计算复杂度较高,所以当群成员较多时,通常需要设计具有更少轮数、更低通信复杂度和内存复杂度的组密钥交换协议.2018 年,Furukawa 等30基于 GSSDDH(generalized supersingular isogeny decisional Diffie-Hellman)假设构造了 n 方 n 1 轮广义 SIDH(generalized SIDH)组密钥交换协议,该方案可以看作两方一轮 SIDH 协议的自然扩展,又使用 SIDH 作为底层密钥交换提出了 n 方两轮 SIBD(supersingularisogeny Burmester-Desmedt)方案,减少了方案的轮数.2019 年,Azarderakhsh 等31基于超奇异椭圆曲线同源提出了一个通信开销接近最优的 n 方组密钥交换协议,基于 SSDDH 假设证明了其在认证链路敌手模型(authenticated-links adversarial model)下的安全性,该方案中每一方将其私钥的一个函数作用于消息参数,并传输结果,该方法不需要额外的成本就能提供身份认证功能,可以防止中间人攻击,并且传输开销最小,不需要可信第三方(trusted third party,TTP).其中,一个临时三方密钥协商的高速软件实现可以提供 80 比特的量子安全性和 120 比特的经典安全性,并且第一个软件实现版本也可以移植到其它平台上.不过,该方案不支持群组成员的添加或删除.同年,Fujioka 等32利用新的密码不变映射(cryptographic invariant map,CIM)提出了两个一轮认证的组密钥交换(authenticated group key exchange,AGKE)协议,并利用 CSIDH 进行实例化,其中 n-UM方案基于 n-way DDH 假设在量子随机预言模型下是安全的,另一个 BC n-DH 方案基于 n-way GDH(gap Diffie-Hellman)假设是可证安全的.672Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023表 1 基于同源的两方密钥交换协议概况Table 1Overview of isogeny-based two-party key exchange schemes时间文献困难问题方案特点20114SSISIDH多项式时间内被攻破20186SSICSIDH达到 NIST 安全类别 I20187SSCDHSIDH-AKECK 模型下安全20188SSTDDHXu-AKECK 认证链路模型下安全20189SSDDHSIDH-UMCK 模型下安全20189SSGDHBiclique SIDHCK+模型下安全201810SSDDHLJAqCK 模型下安全201811SI-APCTSJL消息尺寸和 SIDH 相当,未获得完整安全证明201912SSIG2SIDH素数尺寸更小201913SSIPQDH不需要区分发起者和响应者201913SSIPAKE基于 PQDH 构造201914SSCDHSIDH-EKEBPR 模型下安全201914CSSCDHCSIDH-EKEBPR 模型下安全2019151-Oracle SIDHAKESIDH-3CK+安全201915SSDDHAKESIDH-2CK+安全202016SSIOSIDH计算成本较低202017SSIeSIDH计算速度较快202018Strong-CSIDH-SIDE随机预言模型下安全202019CSI-stDHCSIDHCCGJJ 模型下安全202021SSIB-SIDH素数尺寸更小202122HCDH 和 VCDHSI-X3DHSignal-adapted-CK 模型下安全202123HealSIDH-CDHHealSIDH能够抵抗 GPST 自适应攻击202225SSCDHQi-AKECK+模型下安全2020 年,Boneh 等33基于椭圆曲线间的同源计算提出了第一个构建高效的非交互式密钥交换(non-interactive key exchange,NIKE)协议的框架,该框架建立在一个新原语 CIM 上,但由于需要一个特定的算法将同源曲线乘积的阿贝尔簇作为输入,输出阿贝尔簇的同构不变量,目前还没有获得一个有效的方案.同年,Moriya 等34提出第一个基于 CSIDH 的组密钥交换协议 G-CSIDH,该方案和 CSIDH 使用相同大小的素数模 p 来实现相同的安全级别,G-CSIDH 的安全性可以归约到 CSIDH 的安全性.Moriya利用 G-CSIDH 提出一种生成同源密码系统公共参数的协议,通过归约到 G-CSIDH 再归约到 CSIDH 证明了其安全性,该协议可以应用于任何使用超奇异椭圆曲线作为公共参数的超奇异同源密码系统.另外,Bobrysheva 等35使用树的结构设计了基于同源的组密钥协商方案,并给出了当 n 为 4 时的具体方案流程,未来还可以在选择方案参数方面进一步改进.2021 年,Hougaard 等36提出第一个基于超奇异同源树(supersingular isogeny tree,SIT)的常数轮具有对数级别通信复杂度和内存复杂度的组密钥交换方案,相比之下,SIBD 方案具有线性级别的通信和内存复杂度.该方案可以通过归约到 MSU 安全模型中的 SSDDH 问题来证明其满足后量子安全性.论文中还引入一种新的编译器,可以实现经过身份认证的 SIT 组密钥交换(authenticated SIT刘一丹 等:同源密码方案综述673group key exchange,A-SIT),同时保持复杂性和安全性不变.同年,Takashima37利用从两方密钥交换协议到组密钥交换协议的通用编译器给出两个组密钥交换协议族,其中一个基于 R-LWE 和 SSDDH问题通过使用一个安全的 KDF(key derivation function)获得一个常数轮的组密钥交换协议,但该协议无法获得一个紧安全证明,另一个基于 DSJP(decisional supersingular j-invariants product)和 DSMP(decisional supersingular Montgomery coefficients product)假设分别获得两轮组密钥交换协议 SI-PBD(supersingular isogeny product Burmester-Desmedt)和 CSI-PBD(commutative supersingular isogenyproduct Burmester-Desmedt),并证明了其安全性.2022 年,樊雪君38等首先加速了 SIBD 协议,又使用树形结构,将 SIDH 和 BDII 协议结合提出改进的组密钥交换协议,并证明了该方案在随机预言模型下的安全性,该方案通过将会话密钥计算中的乘法更换为加法提高了效率,两个方案均降低了通信和计算复杂度,效率较高.表2中总结了基于同源的组密钥交换协议的基本情况.表 2 基于同源的组密钥交换方案概述Table 2Overview of isogeny-based group key exchange schemes时间文献困难问题方案特点201830GSSDDHGSIDHn 方 n 1 轮201830SSDDHSIBD2 轮,轮数更少201931SSDDHAzar-GKE-n效率较高,通信开销接近最优201932n-way DDHn-UMG-CK 安全201932n-way GDHBC n-DHG-CK+安全202033n-way DDHNIKE 的框架效率较高202034CSSDDHG-CSIDH安全性归约到 CSIDH202035SSIBob-GKE树的结构202136SSDDHA-SITMSU 模型下安全202137d-DSJPSI-PBD不需要密钥导出函数202137d-DSMPCSI-PBD不需要密钥导出函数202238SSDDHIm-SIBD随机预言模型下安全202238SSDDHIm-SIBDII随机预言模型下可以抵抗被动攻击3.3数字签名基于椭圆曲线同源的数字签名方案与传统的数字签名方案类似,通常由三种算法组成:生成用户公钥-私钥对的密钥生成算法、签名算法和验证算法,并用寻找两条椭圆曲线之间同源关系的困难性假设替代经典密码假设.2012 年,Sun 等39基于超奇异椭圆曲线间的同源计算提出第一个可以抵抗量子计算机的强指定验证者签名(strong designated verifier signature,SDVS)方案,满足不可伪造性、不可转移性和签名者身份的隐私性.2014 年,Jao 等40基于椭圆曲线同源提出第一个基于数论复杂性假设的后量子安全的不可否认签名方案,该方案在 OMSSCDH(one-sided modified supersingular computational Diffie-Hellman)和 OMSSDDH(one-sided modified supersingular decision Diffie-Hellman)假设下分析了安全性,与之前唯一的基于线性码的抗量子不可否认签名方案相比,在性能和带宽方面表现优异.2016 年,Galbraith 等41提出两个基于超奇异椭圆曲线同源图的计算假设的签名方案:第一个方案基于 CSSI 和 DSSP(decisional supersingular product)假设,使用 Fiat-Shamir 变换将 De Feo 等提出的交互式身份认证协议42转换为非交互式签名方案,该方案描述简单,易于实现,在随机预言模型下可以抵抗选择明文攻击,但它使用了特殊的素数,会泄露辅助点;第二个方案基于更标准的计算超奇异椭圆674Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023曲线的自同态环的困难性(等价于计算两条给定椭圆曲线之间的同源)假设,在随机预言模型下可以抵抗选择明文攻击.2017 年,Yoo 等43将 Unruh 的非交互式零知识证明构造应用于 De Feo 等42提出的交互式零知识方案,提出第一个基于超奇异椭圆曲线同源的通用的数字签名方案,并在量子随机预言模型下证明了其 SUF-CMA(strongly unforgeable under chosen message attack)安全性,该方案密钥尺寸小,给出了在 x86-64 平台和 ARM 设备上的运行结果,签名算法大部分可以提前离线执行,减少了计算成本.与 Galbraith 等41提出的基于同源的数字签名方案相比,Yoo 方案的签名尺寸需要 692比特,是后量子安全的;而 Galbraith 给出显著的空间优化,使用时空折中的方法将签名大小缩减到 122比特(如果不考虑不可否认性只需要 62),但签名速度较慢,且 Galbraith 的签名方案是经典安全的,不能抵抗量子攻击.2018 年,Gorrie44对 Yoo 等人的签名方案进行改进,原方案性能指标较差,通信开销较大,修改后旨在提高时间性能且减小签名尺寸.同年,Srinath 等45在 Jao40的抗量子不可否认签名中加入盲签名的性质,提出了基于同源的不可否认盲签名方案(undeniable blind signature scheme,UBSS),并在 SSCDH和 SSDDH 假设下证明了该方案在存在量子敌手下的安全性,具有不可伪造性、盲性和隐蔽性.2019 年,Sahu 等46通过探讨 HHS(hard homogeneous spaces)中构造一般指定验证者签名(desig-nated verifier signature,DVS)的可能性,实现了一个基于超奇异椭圆曲线同源的抗量子指定验证者盲签名 SI-DVBS(supersingular isogeny-based designated verifier blind signature)方案.该方案通过盲签名实现签名者的匿名性,具有不可伪造性、盲性、不可验证性和不可传递性,与 UBSS 方案相比,该方案不需要签署人和验证人之间的交互通信,但让签署人参与验证,消除了交互的通信开销,在电子招标和在线拍卖等特定应用中非常有用.同年,De Feo 等47基于 CSIDH 的类群作用提出一种新的签名方案 SeaSign.该方案在随机预言模型中的选择明文攻击下具有不可伪造性,在 128 比特安全级别上签名尺寸小于 1 千字节,虽然签名比格签名短,但签名速度较慢,成本较高.同年,Decru 等48对 SeaSign 方案进行加速,代价是签名大小略有增加.此外,Beullens 等49改进 SeaSign 方案,获得了第一个实用的基于同源的签名方案 CSI-FiSh(commutative supersingular isogeny based Fiat-Shamir signatures),并证明了该方案在量子随机预言模型中的安全性,还给出一个高效的 CSI-FiSh 开源实现,在同样参数集下,比 SeaSign 的优化版本快 300 倍,签名尺寸缩小为原来的 1/3 在 128 比特安全级别下小于其他任何后量子签名方案.在此基础上,Kaafarani 等50使用 CSIDH-512 参数构造一种 Fiat-Shamir 类型的签名方案 Lossy CSI-FiSh,利用 Kiltz 等提出的“Lossy Key”技术,通过紧归约到 CSSDDH(c