量子计算会是区块链终结?量子计算与区块链抗量子算法
量子计算会是区块链终结?量子计算领域的最新进展,使得很多人对古典密码学的前景感到担忧,像谷歌已研制出了72量子位的量子计算芯片,这距离破解古典密码学需要达到的数千可用量子位级别,似乎不再是那么遥不可及,根据一些人的估算,到2031年,RSA和ECC(椭圆加密)算法被破解的概率大约为50%,而比特币、以太坊等区块链正是运用了古典密码学,虽然比特币使用了双SHA256算法,使其较银行、支付宝等使用的保密系统多了一道防线,但它依然存在着多种攻击向量,似乎量子计算正在成为区块链的达摩克利斯之剑,那么我们需要为此担心吗?
译者认为,需要密切关注,但无需太过担心,到了实在紧急的情况,社区可通过硬分叉的方式,替换掉比特币等区块链所使用的加密算法,而区块链行业的一些研究者,也在不断研究相关的抗量子加密算法,而来自联盟链团队R3的研究团队,在分析了相关攻击向量的同时,提出了一种抗量子签名方案,从结果来看,这一方案更适合用于R3的Corda以及超级账本Fabric。
以下为论文译文:
摘要 – 受区块链架构及现有基于默克尔树(Merkle tree)签名方案的灵感激发,我们提出了BPQS,一种可扩展后量子(PQ)抵抗数字签名方案,它最适用于区块链和分布式账本技术(DLT)。该协议的一个独特特征在于,它可利用专用链或图像结构,以减少密钥生成、签名、验证的成本,以及签名的大小。
相比最近出现的其他改进方案,当一个密钥被重用于合理数量的签名时,BPQS会优于现有的哈希算法,如果有需要的话,它还支持一种回滚机制,可允许实际数量不限的签名。我们提供了该协议的开源具体实施方案,并对其进行了基准(benchmark)测试。
本论文相关术语: 后量子加密,数字签名,分布式账本,区块链,默克尔树(Merkle tree)
一、引言
量子计算领域的最新进展,及其对古典密码学的威胁,促发了更多人对后量子(PQ)研究的兴趣。
更具体地说,由于Shor算法 [1], 量子计算机可以很容易地在多项式时间内分解大整数因子,从而有效地破解RSA。Shor算法的启用,可解决离散对数问题,以及今天的数字签名(例如DSA,ECDSA以及EdDSA),使得它们变得无效[2]。
建立量子计算机的竞赛已经开始了。像谷歌、微软、IBM、D-Wave以及英特尔这样的公司,已经处在了领先位置。然而,截至目前,我们还未能建立一个具有数千个稳定量子位的计算机,可使经典公钥密码技术变得过时。然而,该领域已经有了显著进展,一些乐观的人预测称,在接下来的10到20年 [3], [4]内,一台大型量子计算机可能能够破解非对称加密。
而破解公钥加密系统,其会带来的安全影响将是巨大的,几乎所有的东西都来自HTTPS、VPN以及PKI,而这就涉及到了RSA或椭圆曲线加密算法(ECC)的安全性。而区块链领域同样会被冲击到,并且它可能是受影响最大的领域之一,因为黑客们可以从中获得经济激励,他们可以匿名地访问区块链账户。
为了解决密钥泄露的问题,后量子密码学(PQ cryptography)开始兴起,它将保护我们免受量子霸权的冲击。而我们提出的BPQS解决方案,是基于XMSS方案[5]的一个修改版本。它实际上使用了一个单一的认证路径;因此,它是一条链,而不是一颗树,它只要关注 {一次性和少次}密钥,即它通常最适用于区块链(因为我们想要保持匿名,并尽量减少跟踪)。
与现有方案相比,当只需要签名一次或少量次数时,我们的方案表现会更优。与一次性签名方案(OTS)不同的是,BPQS方案提供了一种回滚机制,可轻松支持多次签名。 据我们所知,这是第一个可利用现有区块链或图形结构,来减少签名成本的签名方案(即使我们计划签署多次也是如此)。
这使得现有的多次状态签名方案对于区块链应用而言会变得过时。而且,事实上, BPQS完全基于哈希函数,因此其实施不需要特殊的数学理论,这使得它成为了现有或新区块链应用的有力签名方案候选者。
二、 量子计算
受市场对更高效计算及解决先前不切实际问题能力的需求推动,量子计算从基础理论研究,到现实研究的进程正在快速移动。10年之前,很少有实用量子计算机的证据。然而到了2018年,谷歌推出了Bristlecone[6],一种新的拥有72量子位的量子计算芯片,它比IBM在2017年公布的50量子位处理器领先22个量子位。
我们也应该提一下D-Wave这家公司,其最近宣布了一个2000量子位的处理器[7],然而,有报道称D-Wave的量子加速分析是值得商榷的[8]。总而言之,尽管我们仍然需要更多的研究和实验,才能使量子芯片保持稳定且具有低的错误率,但量子计算的技术在进步,这已经是一个不争的事实。
A. 对密码学的影响
量子技术带来了新的安全挑战,如上所述,它会弱化经典密码学的前景。由于Shor算法,广泛使用的基于离散对数的公钥密码系统,被认为在后量子(PQ)时代是会被破解的。根据一些人的估计[3],到2031年,RSA和ECC算法被破解的概率大约为50%。此外,Grover算法 [9]也可能影响对称加密和哈
我们也应该重视量子技术的发展,有怀疑论者 [10]认为,量子霸权将永远达不到数千可用量子位[2]的级别(即能够打破经典密码学所需要的程度)。尽管量子计算机何时可达到这种程度,目前仍然是存在不确定性的,但学术界和业界的研究及开发仍然是有意义的。
也有人在尝试结合经典和后量子算法[11], [12],以更好地为量子启示录(假设它会发生的话)做好准备。这里还应该提到标准化机构,比如NIST,它已经开始研究标准化的后量子(PQ)算法[13], [14]。
欧洲电信标准研究所(ETSI)则会更加谨慎一些,该机构建议,任何需存档加密数据至2025年(或更久)的组织,都应该担心量子计算机的威胁 [15]。而在区块链和分布式账本领域的人们,更应该关注量子计算,因为公钥所持有的资产/币,可能会经历几十年的时间。
B. 对区块链和分布式账本技术(DLT)的影响
传统的区块链,如比特币和以太坊,采用了经典的公钥加密技术来签署交易,而这些网络被认为是容易受到量子计算攻击影响的。其他系统,例如zCash和Quorum,严重依赖于特殊的椭圆曲线以提供零知识证明功能,而一次椭圆曲线算法违约(ECC breach),便会威胁到这些账本的完整性 [16].
这将是重大的安全隐患,它会导致网络被全面破解,而大多数区块链使用了公钥密码哈希生成的地址来减轻这种威胁(译者注:例如比特币使用了双重SHA256)。
这个安全性的附加层,意味着公钥只有在其参与第一笔交易(即花费比特币)发生后,它才会暴露给账本。直到这一点,只有哈希接收方密钥(地址)被暴露,因此像Shor算法攻击并不适用于这个阶段。
但是,以下攻击向量仍然是适用的,即使当哈希密钥被利用时:
1、地址重用 :当一笔交易被签名时,公钥就会被揭露,因此,与其相关联的地址就不再是安全的了。尽管我们可建议每交易一次使用新的地址/密钥,但旧的比特币客户端和某些矿池仍然会重复使用地址;
2、被遗弃的币/资产:如果它们的相关地址不是通过哈希生成的,这些旧地址的公钥就会被暴露,例如2012年之前的比特币;
3、正在进行当中的交易:一旦你把一笔交易广播到网络上,并且它还没有被区块链所接受,那么这些交易就很容易受到攻击。当然,这个攻击的窗口机会是有限的,但理论上还是可能的,在交易被合法执行之前,攻击者可恢复私钥,然后用其签名另一笔交易,将资产转移到自己的地址当中;
4、交易被拒/失败的情况:如果签名的一笔交易没有通过,例如,由于给出的交易费过低,或者有恶意方阻止交易中继,或在验证过程中出现脚本错误,那么密钥将会受到攻击;
5、多重签名交易/混合交易:如果使用CoinJoin协议 [17],这会在交易完成之前向其他各方揭示公钥;
6、单个地址的公告:公告和使用相同的地址,例如筹集资金,将会暴露第一次消费交易的公钥,因此会将后续资金收益置于风险之中。
通常社区会建议的解决方案,是升级签名算法,使其能够抵抗量子计算。然而,这总是会导致一次区块链的硬分叉,而这会引入各种复杂性。也有一些区块链解决方案已经支持了后量子技术,例如量子抵抗账本 (QRL) [18]、IOTA [20] 以及Corda[22] ,而应用BPQS签名方案,可减少签名大小,同时提供了一种回滚机制,以允许用相同的密钥签名多次。
三、使用相同密钥进行签名的场景
OTS哈希方案要求只使用密钥一次,否则安全性就会受损。然而,在区块链当中,有很多是需要使用相同密钥进行多重签名的场景:
1、如上一节内容当中所述,交易可能会失败或被拒绝,这就需要额外的签名来进行解决。
2、密钥所有权的证明,其中甲方需要去签署一则由(挑战性)乙方提供的消息,然后让乙方验证这个所有权;
3、偿付能力证明,所需最小数量资产的所有权证明,而不会泄露任何进一步的信息。而解决这一问题的办法,在于进行独立审计,并用所有者的私钥记录在一笔“发送给自己”的交易当中;
4、分叉区块链,其中地址(以及相关联的密钥)会在分叉链上被复制,随后在每个分叉链中使用,来自相同地址的重复交易(使用OTS方案进行签名)就违反了一个密钥只能使用一次的条件,因此,OTS签名方案的强度将会减半。
5、资产的战略性双重支出,它可导致交易被拒绝,这种情况也可能是故意锁使一笔等待的交易被拒绝。这种情况有可能会在意外支出的场景下发生。用相同密钥签名一笔复制交易,可导致两笔交易同时失败,且它会导致不良的后果,即密钥被重复使用。
四、基于哈希的后量子(PQ)数字签名
A.一次性签名(OTS)
基于哈希的签名方案可追溯到1979年,这得益于Lamport OTS(一次性签名)方案 [24]。
Lamport方案背后的逻辑是明确的:签名者生成每个比特所需要被签名的随机值对,以及形成私钥的对。公钥是
由这些值的哈希形成的。而要签署一则消息,签名者按位读取消息,并显示一个值,每个秘密对取决于比特值。然后,验证者可验证所有秘密值的哈希,是否与公钥中的相应哈希值相等。虽然Lamport OTS哈希计算被认为是快速的,但其密钥和签名大小则相对较大。
例如,如果SHA256被用作底层哈希函数,则公钥是由512个256位的哈希输出组成的(每个位1个哈希对),而签名是由256个秘密值组成的(每个256位)。如果我们总计一下密钥和签名数据,它们就需要占用24.5 kB,类似的,如果运用的是SHA512算法,则大约会占用98 kB;
对原始算法的进一步增强[19],[25], [26],可显著减小密钥大小。目前,WOTS算法[19]及其变体被认为是最为有效的密钥和签名压缩方法,而Bleichenbacher和Maurer的图形方案 [26],尝试在签名大小,以及每个消息位的哈希函数求值数方面,达到最好的效率,
作为注释,OTS方法之间的主要区别之一,在于需要的安全假设是否与抗哈希函数相抵抗,以及是否使用额外的位掩码。目前,WOTS-T [27]被证明在QROM模型当中是安全的,其被认为是WOTS系列方案[19]最有希望的候选者,因为只有一个额外的种子值需要和公钥一起,用于计算所需的位掩码,而其安全性不会受到“生日悖论”的影响,它还引入了所有哈希的键控函数调用,以防止多目标进行第二次原像攻击。后者会导致更短的公钥和哈希输出大小。
B. 少次和多次性签名
虽然当前有很多方法将一次性签名方案转变为多次性签名方案[5], [28]–[30],一种流行的方法,是使用默克尔认证树(Merkle authentication tree)。使用默克尔树,可发布的签名总数是在密钥生成时定义的。而这样做的主要好处,在于它的短签名输出以及快速验证,而缺点是相对较长的密钥生成时间,并且它们是有状态的。图1描绘了一个4次(最大值)默克尔树签名方案。
图1:最多能签名4则消息的默克尔树签名方案,如果我们用OTS1方案签名,暗节点就表示所需的认证路径。
而转向无状态的少次签名方案,就需要额外的复杂性,以及更大的签名输出。HORS [29] (及其扩展HORST [23])方案是目前使用最多的多次无状态签名方案,例如SPHINCS [23]。
多次哈希签名方案可通过结合上述的 {一次性和少次性}方案进行构建,并且它们可被分为两类:有状态的(例如XMSS,LMS)[31]和无状态的(例如SPHINCS,SPHINCS +,Gravity,Simpira,Haraka)[23],[32] – [35]。有状态的方案通常会产生较短的签名,但它们需要一种机制来保持状态(已使用了哪些路径/密钥)。
另一方面,无状态的方案是从顶部适度大小的默克尔树或树层开始,而不是在底部使用OTS签名,它们使用了一种少次性签名方案。后者允许它们随机选取索引,因此不需要跟踪路径状态。而无状态方案的不足之处在于它们的签名大小,例如,在SPHINCS-256 [23]方案当中,每个签名的大小会有 41 kB。
少次性和多次性哈希签名方案之间,并不总是很清楚的。在文献当中,少次性签名方案通常指无状态方案,例如BiBa [28], HORS [29] 以及 HORST [23],但在很多实际应用当中,这些签名还是不够的。
本文采摘于网络,不代表本站立场,转载联系作者并注明出处:http://www.fjxmta.com/zmt/36436.html