综述:基于等位基因的密码学:关于技术进展、攻击分析及未来方向的全面综述
《Computer Science Review》:Isogeny-based cryptography: A comprehensive review on advancements, analysis of attacks, and future directions
【字体:
大
中
小
】
时间:2025年12月22日
来源:Computer Science Review 12.7
编辑推荐:
Dheerendra Mishra | Rohit Raj Sharma
印度博帕尔莫拉纳·阿扎德国立技术学院数学、生物信息学与计算机应用系,邮编462003
**摘要**
量子计算的最新发展为传统密码学方法带来了重大挑战,尤其是那些依赖于整数因子分解和离散对数的方
Dheerendra Mishra | Rohit Raj Sharma
印度博帕尔莫拉纳·阿扎德国立技术学院数学、生物信息学与计算机应用系,邮编462003
**摘要**
量子计算的最新发展为传统密码学方法带来了重大挑战,尤其是那些依赖于整数因子分解和离散对数的方法。为应对这些挑战,人们提出了多种后量子密码(PQC)技术,包括基于格、哈希、编码、多元方程和同源性的密码系统。每种技术都基于复杂的数学问题,即使使用量子计算机也难以解决。其中,基于同源性的密码学因其较小的密钥大小而受到广泛关注,成为开发高效后量子密码原语的领先候选者。本文深入探讨了基于同源性的密码技术,重点介绍了密钥交换、零知识证明(ZKP)和签名协议。文章首先阐明了椭圆曲线、同源性以及相关协议的基本概念,随后讨论了当前方案面临的挑战,并探讨了旨在提高安全性、可扩展性和功能的潜在研究方向。
**引言**
量子计算的最新进展威胁到了传统密码技术。1994年,Peter Shor 提出了一种突破性算法[1],该算法可以使用可扩展的量子计算机在多项式时间内解决整数因子分解问题(IFP)和离散对数问题(DLP)。鉴于传统密码系统在量子计算时代可能失去安全性,人们提出了多种后量子密码策略[2]。前四种后量子密码原语是:基于格的密码学[3]、基于哈希的密码学、基于编码的密码学和多元公钥密码学[4]。
基于格的密码学已成为量子计算时代实现安全性的一个有前途的选择。依靠解决格问题难度的密码系统因其实现简单和日益实用而变得越来越重要。最初的基于格的签名协议见[5]。GPV方案的安全性基于最短整数解(SIS)问题的复杂性。该方案面临多重挑战,特别是在密钥大小、效率和参数选择方面。为此,研究人员改进了GPV方案,提高了空间效率和执行时间,并实现了这一优化版本。此外,还开发了一种基于环的增强版本,配置更加高效。实验结果表明,带有新型陷阱门结构的GPV方案与当前广泛使用的签名方案相比表现良好[6]。多种应用需要传输公钥和签名,因此Dilithium项目致力于减少它们的总大小。尽管避免了高斯采样,Dilithium在现有基于格的签名协议中实现了最小的总大小。针对签名系统的经典故障攻击利用错误签名和正确签名的配对来推断私钥,但这些攻击仅限于确定性签名。为了防范此类威胁,Dilithium采用了随机化方法,确保即使对于相同的消息,每个签名也是唯一的。Dilithium已被NIST认可为后量子标准提案,但它面临着由[7]提出的签名校正攻击,这种攻击利用Dilithium的数学框架以及错误签名和公钥来推断秘密密钥位。研究人员继续提出新的签名协议,以期超越Dilithium的性能。
多元公钥密码学(MPKC)是一类能够抵御量子威胁的密码协议,其原理基于在有限域上解决多元多项式方程的难度。这类方案主要针对多元二次(MQ)系统,这被认为是一个NP难题,据信能够抵御量子计算攻击。在MPKC系统中,通过将一个中心可逆映射(通常是二次的)与仿射变换结合,生成一个公共映射,从而掩盖了陷阱门的结构[8]。早期的MPKC方法包括Matsumoto–Imai的C?方案(1988)[9]和Patarin的隐藏域方程(HFE,1996)[10]。这些创新后来伴随着Oil-Vinegar(OV,1997)和Unbalanced Oil-Vinegar(UOV,1999)签名算法[11]的出现。尽管C?和最初的HFE可以通过代数方法被攻破,但引入减法或醋类修改的变体提高了其鲁棒性。进一步的进展产生了多层方案,如Rainbow(2005)[12]和紧密组织的框架如GeMSS[13],实现了既紧凑又高效的签名。
在NIST对PQC的标准化过程中,基于多元公钥密码系统的方案(MPKC),如Rainbow和GeMSS,推进到了数字签名类别的第三轮。然而,最近针对MinRank漏洞的攻击严重削弱了这些方案,导致NIST在2022年不再考虑它们。因此,没有MPKC方案被选为标准化方案。尽管如此,人们仍在持续研究新的变体(例如MAYO[14]、SNOVA[15]、QR-UOV[16])。MPKC具有多个吸引人的特性:它对量子攻击具有强大的理论抵抗力,依赖于小域上的简单代数运算,实现了高速的签名和验证过程,并提供了紧凑的签名大小(例如,Unbalanced Oil and Vinegar(UOV)签名通常约为100字节)。此外,MPKC还支持盲签名、基于组的签名和基于身份的签名等复杂功能[8]。然而,其缺点包括较大的公钥大小(通常达到数百千字节)、易受代数和结构攻击的脆弱性[17],以及缺乏基于MPKC的强大高效加密方案。尽管存在这些缺点,MPKC仍是后量子密码学领域的一个活跃研究课题。
**基于编码的密码学**
基于编码的密码学由Robert McEliece于1978年[18]提出,它依赖于解码一般线性编码的NP难题来确保安全性,从而既能抵御经典攻击也能抵御量子攻击[19]。当前的研究重点在于优化参数和使用结构化的编码来最小化密钥大小。NIST第四轮评估中的候选方案包括Classic McEliece[20](使用二进制Goppa编码以实现保守的安全性)和BIKE[21](使用准循环MDPC编码以实现更高效的密钥)。这些密码方案主要用于TLS握手、VPN和安全存档存储中的密钥封装机制,在这些场景中保持长期机密性至关重要。它们的优点基于经过充分分析的难度假设、快速的矩阵-向量计算以及持久的密码分析鲁棒性;然而,它们也存在缺点,如较大的公钥大小(通常数百千字节)、较大的加密密文大小,以及某些变体的非零解密失败率。
NIST的标准化工作显示了基于编码的密码学作为一个全面且强大的密码系统的巨大潜力,集成了加密、密钥交换和数字签名功能。当前的研究努力旨在进一步减小密钥大小,并将基于编码的原语与基于格或哈希的方法相结合,以优化性能和安全性[22]、[23]。
**基于哈希的密码学**
基于哈希的密码学的安全性依赖于密码哈希函数的抗碰撞特性。它主要用于设计签名协议[24]。哈希函数的简单改进过程和有效实现提高了基于哈希的签名的效率和安全性。主要的签名协议包括Merkle签名方案[25]、SPHINCS[26]和NIST标准化的SPHINCS+ [27]。
第五种也是最近几十年最受关注的后量子密码原语是基于同源性的密码学(IBC)。可以将其视为后量子框架下的椭圆曲线密码学[28]。其数学表述源自两个椭圆曲线之间的态射,其中域中的单位元素映射到陪域中的单位元素。由于椭圆曲线的DLP是当前密码系统中现有数学难题(如整数因子分解和乘法子群中的离散对数)中的最短密钥算法,基于同源性的密码学也继承了这一特性,并且在其他所有后量子密码系统中具有最小的密钥大小。
同源性最初由Couveignes在1997年引入到密码学中,但未发表,仅私下交流[29]。2004年,Rostovtsev和Stolbunov独立发现了这种方案。第一个基于同源性的密码学方案于2006年正式发表,称为Couveignes-Rostovtsev-Stolbunov方案(CRS Key Exchange [30])。该方案要求椭圆曲线的基数能被多个小素数整除,但找到这样的椭圆曲线非常繁琐,因此该方案仅停留在理论阶段。Charles等人于2007年提出了基于CGL哈希函数的超奇异椭圆曲线,开辟了这一领域的新研究方向[31]。2011年,Jao和De Feo提出了基于类似同源图形的Supersingular Isogeny Diffie-Hellman(SIDH)[32]签名协议。这是第一个利用椭圆曲线的超奇异性质的经典密码协议。超奇异椭圆曲线的自同态环是非交换的,Jao等人利用这一性质构建了SIDH。经过进一步改进后,如[33]、[34]、[35]中的改进,SIKE[36]作为KEM版本在2017年成为NIST PQC标准化第三轮的候选方案。考虑到过去几年同源性方法的诸多进展,现在这些方法已经错过了进入NIST PQC流程的机会。
**基于同源性的密码学**
IBC最著名的密钥交换方法是Commutative Supersingular Isogeny Diffie-Hellman(CSIDH)方案,由Castryk等人于2018年提出[37]。该方案基于对CRS方案[30]的改进,并利用其交换框架开展了广泛的研究,包括数字签名等高级协议。然而,基于同源性的PQC原语容易受到侧信道攻击,例如功耗分析、故障注入和Timing攻击。关于这些攻击的更全面讨论及其推荐对策见[38]。SIDH和CSIDH为许多认证协议的构建奠定了基础,如不可否认签名[39]、不可否认盲签名[40]和数字签名协议[41]、[42]、[43]。这些数字签名协议配备了零知识证明,确保系统中的公钥正确生成,并且公钥生成器知晓相应的私钥。总体而言,基于同源性的密码学在后量子时代塑造安全数字未来中发挥着重要作用,为密钥交换和数字签名提供了坚实的基础。
**总结**
本调查旨在提供基于同源性的密码学(IBC)领域的全面且易于理解的概述,这是一个新兴的后量子密码研究领域。目前,关于IBC及其数学基础的理解分散在许多出版物和协议中。迫切需要一项全面的调查来统一这些研究,阐明当前的进展并规划未来的研究方向。本文系统介绍了依赖椭圆曲线间同源性识别的密码方案。通过本文,读者可以深入了解基于同源性的密码方案,掌握构建这些方案所需的数学基础。我们详细探讨了利用椭圆曲线间同源性的关键密码方案,包括密钥交换机制、数字签名算法和零知识证明(ZKPs)。分析了当前的基于同源性的方案,指出了其漏洞,并观察到了利用这些弱点的最新攻击。我们还指出了该领域中的潜在研究方向和需要进一步调查和分析的关键领域。我们的工作全面分析了各种基于同源性的系统在安全性和性能指标之间的权衡。相比之下,早期的调查[44]、[45]、[46]、[47]主要关注特定的基于同源性的密码方案。Beullens等人[44]讨论了证明同源性及其应用的挑战,而Drzazga和Krzywiecki提供了关于SIDH及其构建协议的概述。Maino等人[46]简要介绍了CSIDH的漏洞和发展情况。Mishra等人[47]记录了SIDH和CSIDH的进展,但对其在签名协议或多用户环境中的应用的讨论有限。虽然[46]、[47]主要探讨了基于同源性的密码学(IBC)的基础,但我们的工作展示了其在其他后量子密码原语中的应用。表1提供了比较性总结,强调了我们研究的独特贡献及其更广泛的范围。第2节概述了本工作所需的基础概念。第3节介绍了CRS方案的基本信息。我们在第4节讨论了SIDH协议,分析了现有的攻击手段,并提出了应对这些威胁的对策和变体。第5节专门讨论了CSIDH协议,探讨了其不足之处、安全挑战以及建议的缓解措施和变体。第6节讨论了基于同构的签名方案和零知识证明,并总结了基于超奇异同构的签名方案。第7节评估了多方协议及其在同构中心密码学中的应用。第8节强调了我们的分析见解,并简要介绍了基于同构的密码学的进展,第9节指出了存在的局限性并提出了未来的研究方向。我们的综合调查在第10节结束。此外,图1展示了所涵盖的主题,提供了讨论焦点的有组织概览。
**初步说明**
我们在整篇文章中使用了以下缩写(表2)和符号表示法(表3)。
**Couveignes–rostovtsev–stolbunov方案(CRS)**
CRS是一种无需交互的关键交换协议。它基于类似于Diffie-Hellman密钥交换的理想类群操作。CRS的数学运算起源于理想类群cl(O)与以O为导向的普通椭圆曲线集合之间的相互作用:
$$
\clubs(O) \times E(F_p) \xrightarrow{[a], E_0} \xrightarrow{[a]\clubs(E_0)
$$
cl(O)的交换性质允许执行类似Diffie-Hellman的密钥交换。公钥是从这些等价曲线中得出的。
**超奇异同构Diffie-Hellman(SIDH)**
Childs等人的工作[55]指出了现有密码框架在面对量子威胁时的脆弱性,从而激发了大量研究工作,旨在创建一个强大且有效的IBC协议。由于SIDH不依赖于自同态环的交换性质,因此不受[55]发现的影响。该概念基于在具有固定度的超奇异?-同构图上的随机游走,从预先选定的点开始。
**交换超奇异同构Diffie-Hellman(CSIDH)**
在SIDH取得一定成功之后,人们逐渐忘记了类似CRS的系统。构建一个类似于CRS的高效系统仍然是密码学家面临的挑战。Castrick等人通过成功实现超奇异椭圆曲线解决了CRS的挑战。由于超奇异椭圆曲线的End(E)是非交换的,CSIDH使用了其交换子环,该子环与四元数代数中的一个序同构。
**基于同构的数字签名和ZKP**
我们经常遇到这样的情况:我们拥有秘密信息,需要披露部分信息,但只想揭示所需的部分而不暴露其他秘密。这就提出了一个问题:如何在不暴露其他秘密的情况下验证新披露的信息。证明系统允许证明者在不透露任何超出有效性的信息的情况下让验证者相信某个声明是真实的,这种系统被称为零知识证明。
**探索基于同构的密码学中的多方协议**
多方协议确保没有任何一方能够单独访问另一方的输入,也没有人能够在没有所有参与者集体合作的情况下修改协议。多方密码协议在当今的各种应用中发挥着关键作用。例如,Threshold ECDSA [107]广泛用于多签名加密货币钱包中以提高安全性,而zk-SNARKs [108]支持保护隐私的区块链交易。对这类协议的依赖日益增加。
**观察分析**
本节详细分析了基于同构的密码学文献。我们对IBC与其他后量子对应方案进行了全面比较,评估了关键参数,如密钥大小、签名大小和性能。我们还为未来的研究制定了路线图,重点关注提高效率、减少处理开销和探索新应用等主题。
**讨论**
基于同构的密码协议的计算成本是一个显著问题。与其他后量子数字签名(特别是基于多变量多项式签名系统的签名)相比,基于同构的签名方案显示出明显的效率低下。这种效率低下是实际应用基于同构的签名方法及其他相关协议的主要障碍。
**结论**
由于基于同构的密码学与同构映射、类群操作和四元数代数等基本数学原理的一致性,可以利用同构来开发各种密码协议,包括密钥交换、加密、签名、认证和封装。其中,CSIDH是最先进的基于同构的密码系统之一,目前是一个活跃的研究课题。与SIDH相比,CSIDH具有明显更紧凑的密钥大小。
**利益冲突声明**
作者声明他们没有已知的财务利益冲突或个人关系,这些可能会影响本文报告的工作。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号