内容简介:以下为论文译文:作者: Konstantinos Chalkias∗ , James Brown† , Mike Hearn‡, Tommy Lillehagen§,Igor Nitto¶, Thomas Schroeterk (R3)联系方式:Email: ∗konstantinos.chalkias@r3.com, † james.brown@r3.com, ‡mike@r3.com, § tommy.lillehagen@r3.com, ¶igor.nitto@r3.com, k thomas.sc
译者认为,需要密切关注,但无需太过担心,到了实在紧急的情况,社区可通过硬分叉的方式,替换掉比特币等区块链所使用的加密算法,而区块链行业的一些研究者,也在不断研究相关的抗量子加密算法,而来自联盟链团队R3的研究团队,在分析了相关攻击向量的同时,提出了一种抗量子签名方案,从结果来看,这一方案更适合用于R3的Corda以及超级账本Fabric。
以下为论文译文:
区块链后量子(PQ)签名
作者: Konstantinos Chalkias∗ , James Brown† , Mike Hearn‡, Tommy Lillehagen§,Igor Nitto¶, Thomas Schroeterk (R3)
联系方式:Email: ∗konstantinos.chalkias@r3.com, † james.brown@r3.com, ‡mike@r3.com, § tommy.lillehagen@r3.com, ¶igor.nitto@r3.com, k thomas.schroeter@r3.com
摘要 -受区块链架构及现有基于默克尔树(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]也可能影响对称加密和哈希,但目前我们不知道如何获得相对传统计算机更多的二次加速,从而,可通过增加密钥/输出大小来保证PQ的安全性。我们也应该重视量子技术的发展,有怀疑论者 [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],但在很多实际应用当中,这些签名还是不够的。另一方面,多次性签名方案可以被配置,以允许高度交互的环境下,重用相同的密钥对(可以用很多年)。Gravity SPHINCS [33]方案的作者称1万亿(2^40)次签名是合理的上限,而SPHINCS-256 [23] 签名方案则允许最多1千万亿(2^50)次签名。而在实践当中,人们可以参数化一个多次签名方案,以支持几次或多次签名。
C.哈希函数的速度和安全性
对于拟议项目的整体安全性而言,底层哈希算法显然是非常重要的。几个因素会影响算法的选择,包括 速度 、 安全性水平 以及 可用性;例如,可以运用什么硬件功能来改善运行时的性能。然而,要建立的第一件事,就是算法需对后量子(PQ)攻击具有抵抗力。SHA-2和SHA-3算法支持多种摘要大小,即224, 256,384和512位[36],[37]。我们通过Grover算法提供的改善搜索速度,来观察这一点,碰撞阻力可以从所选摘要的一半大小减少到三分之一。因此,在存在大规模量子计算机的情况下, 384位版本的SHA-2和SHA-3算法将提供128位防碰撞安全性。而256位的版本,只能提供85位安全性 [4]。
此外,我们观察到,针对256位版本SHA-2和SHA-3算法的量子原像攻击,可分别通过2^153.8和2^146.5次代码循环完成[38]。
通过这两个观察,基于哈希安全性方面的考虑,SHA256算法其实已经不太合适了,但它仍然是相对安全的。 还需要提到的是,后量子(PQ)算法相对于经典van Oorschot和Wiener哈希碰撞算法,在性价比上会更糟糕,即使是在乐观的量子计算机发展速度假设下 [39]。
根据eBACS [40]中提供的性能测量,我们已经评估了SHA-2、SHA-3以及 BLAKE2算法在通用CPU上的相对性能。我们特意选择了英特尔、AMD和ARM处理器来覆盖典型的桌面和移动计算机。
我们从表1可看出,每个字节的周期数随输入的大小而减小,而当输入超出区块大小时,下降率自然会变平。
还需要注意的是,不同版本的SHA-3,通常其表现会比它们的SHA-2对手要差。其中的一个原因,在于SHA-1和SHA-2都有现代处理器更多的硬件支持(例如英特尔®SHA扩展提供的指令集扩展)。请注意, 尽管SHA-2算法没有提供针对长扩展攻击的保护,但它提供的位安全性与SHA-3是类似的。通常而言,基于哈希的后量子签名方案(包括BPQS),不容易发生此类攻击,因此,就SHA-2和SHA-3之间的比较,我们会考虑使用SHA-2,因为它有更好的性能优势。
如果性能很重要,我们也可以考虑采用获较少支持的BLAKE2b [41] 算法。但我们要强调的是,这种算法与上述算法相比,会缺少广泛的库支持。
表1:SHA-2、SHA-3和Blake的性能度量
a:基于ECRYPT II在eBACS中报告的数字[40]; - Intel - amd64, genji122, supercop-20171020 - AMD - amd64, genji262, supercop-20171020 - ARM - armeabi, odroid, supercop-20160806
五、为一次性密钥定制的区块链化后量子签名
大多数(如果不是所有的)少次哈希签名方案都使用了默克尔树(Merkle tree)。一个基本默克尔树(Merkle tree)签名方案最多可签名的信息数量是2^h,其中h是树的高度。此外,所有子叶(密钥)应该是在密钥生成期间计算以形成根。由于上述原因,要构建一棵高度为h = 40的树,这样的密钥生成将被认为是不切实际的,因为我们需要计算2^40 个OTS密钥,而每个OTS密钥都需要很多哈希调用(例如Lamport OTS就需要512哈希调用,或者当使用SHA256的WOTS (w = 16)时就需要67哈希调用)。保持密钥生成时间切实可行的同时,还可以允许大量签名使用一棵多层次树。
BPQS是XMSS类协议[5]的一个简化单链变体,字面上讲,它是基础默克尔树签名方案(见图1)的一种扩展。 BPQS理论上可签名很多次,但其设计着眼于短和快速的一次性签名,如果有需要的话,有额外的选项可重新签名。以上的要求是典型的区块链或分布式账本技术(DLT)所需要的,因为使用一次性密钥可保持匿名性。但是,很多事情可能会出错,例如,一笔交易可能无法通过,或者区块链中可能会出现分叉,在这种情况下,应该能够在不损害安全性或冻结资产的情况下签署多次(见IOTA的问题[21], [42])
此外,BPQS的另一个好处在于,它对于相反要求(用同一个密钥签名多次)而言也是一个理想的候选方案,这个有趣的属性是因为,区块链和分布式账本系统的底层图形结构,较其他基于哈希的后量子(PQ)解决方案而言,它以最小的代价有效地允许多次签名。这是通过引用过去已被使用的相同BPQS密钥的区块(或交易)来实现的。简而言之,只有一小部分的新签名是需要被提交的。实际上,因为先前的交易已经在账本上得到了验证,因此验证者们不需要验证路径的其余部分,因为它在过去已经被验证过了。这个特性使得BPQS对基于公证的分布式账本特别有用,例如Corda [22]以及Fabric [43],因为公证节点通常会用相同已知的密钥来签名交易。
A. BPQS方案
BPQS需要一个基层的OTS方案。理论上,任何OTS方案都是可应用的,但我们的方案与 XMSS系列协议的逻辑是相同的,因此我们会选择WOTS [19]变体,使用L树以及位掩码的生成定义了安全假设以及证明,类似于XMSS [5],其多级版本XMSS-MT[44]以及XMSS-T [27]。此外,根据[39],使用量子算法的碰撞阻力实际上会更便宜,因此它类似于Gravity SPHINCS [33]方案,而位掩码和L树可能会被省略。
你也可以说BPQS是XMSS系列方案的一个子集,它主要面向的是快速一次性签名。其中存在的主要区别在于,XMSS通过使用哈希树克服了每个密钥对消息的限制,其会减少很多OTS验证密钥对一次公共XMSS根密钥的真实性;相反,BPQS使用了一个包含小型2子叶默克尔树的链。从几何定义上,XMSS在宽度和高度上都会增长(见图1),而BPQS仅在链高度上成长(见图2)。总而言之,我们强调,BPQS是一个通用的区块链结构,其中的区块是“微小”的默克尔树,这意味着,根据应用的要求,它是可被参数化的。如果遮掩码得到应用,它们的确定性生成应该遵循与相应XMSS系列方案相同的逻辑。
BPQS签名方案有两个基本构建部分:
- BPQS-FEW :其严格支持少次性签名,如图2所示(左侧);
- BPQS-EXT :理论上可扩展到支持多次性签名,见图2(右侧);
在BPQS-FEW当中,所有的密钥都是在密钥生成过程中预先计算的,每个额外签名的惩罚,仅仅是1个额外的哈希输出,但它不能扩展到实际支持“无限的”签名。
另一方面,BPQS-EXT最初只需要两个OTS密钥,这与BPQS-FEW形成了对比,在一个OTS回滚密钥的每个2子叶默克尔树的左侧叶,当有需要时,它可被用于签署下一个区块。不幸的是,可扩展属性是需要付出代价的,每个新签名都需要一个额外的WOTS密钥。
图片2 :BPQS-FEW(左侧),一个少次性签名方案。BPQS-EXT(右侧),一个线性可扩展多次性签名方案;
完整的BPQS方案通过一种方式(其中BPQS-FEW链中的最后一个子叶在一个BPQS-EXT回滚密钥中),从而结合了BPQS-FEW以及BPQS-EXT。这种技巧,允许我们把少次签名方案变体转换为多次签名方案。实际上,BPQS-EXT可以被认为是BPQS的一个特例,其中它没有初始的BPQS-FEW链。
图3: 完整的BPQS协议,其具有高度为3的BPQS-FEW顶层和一个BPQS-EXT回滚密钥,以允许扩展性。
BPQS的参数包括:
1、使用的WOTS变体(例如,WOTS-T [27]); 2、Winternitz参数(例如w = 16),其定义解释初始哈希的基础。类似于XMSS [5],w 定义了每个WOTS链的实际大小,这反过来会影响签名大小。请注意,文献中对Winternitz参数的说明没有达成一致。例如,在 LMS [45]当中,它被定义为2^w,因此 wBPQS = 16 = 2^4 这就相当于wLMS = 4, 3、底层哈希函数(例如SHA384); 4、预先计算的OTS密钥的数量,即初始值高度(例如,h = 4);
B. 混合型BPQS
BPQS的可扩展性属性,可实现各种自定义结构。 BPQS可被用作一个构建块,将任何哈希签名方案转换成一种 {一次性或少次}优化方案。例如,在图4当中,BPQS-FEW被用作第一个(较短的)签名,然后它回滚到另一个后量子(PQ)方案。虽然在描述的方法当中,回滚(其它)后量子(PQ)方案的密钥对应该是先验已知的和预先计算的,你也可使用类似的方式来应用BPQS-EXT,所以,这不一定是一个要求,而“其他”后量子(PQ)密钥仅在(几次性)签名耗尽时才会被生成。
而且,如果“其他”后量子(PQ)方案是无状态的,比如说SPHINCS,那么最终的协议差不多就是一个“启动时有状态,然后转到无状态”的方案。
应该强调的是,“其他”后量子(PQ)方案可能会是另一个BPQS方案,所以最终可以创建一个不同BPQS方案的链。后者会导致较短的签名,以及每次仅使用BPQS-EXT来扩展它。
关于“其他PQ关键参数”,则如图4所示,重要的是,需要一些方案发布位掩码(或者在XMSS-T [27]中的种子)作为初始公告公钥的一部分。否则,它将允许敌对方在一次伪造活动中选择种子/位掩码。然而,如果BPQS使用具有更大输出的哈希函数(例如SHA384 或者SHA512),这可能就不是必需的,因为其所提供的抗量子碰撞攻击安全性,仍然足以防止此类攻击。
图4: 一种通用的BPQS协议(BPQS-VERS1),其带有高度为3的顶层BPQS-FEW,其最后的一个根是另一个后量子(PQ)方案(例如XMSSMT [44] 或SPHINCS+ [32])的公钥。
C. 组合后量子(PQ)方案
如前所述,如果有需要的话,BPQS可以回滚到另一个后量子(PQ)方案,通过应用一个类似的逻辑,图5展示了将多个后量子(PQ)方案组合成一个方案的多种定制模型。方法是非常简单的,但它允许非常有用的结构,例如在图5 A和B当中的“有状态和无状态”方案,或者在图5 C中的“带有无状态回滚的有状态”方案。后者为集群环境(其中多个节点需要在签名状态上达成共识)提供了一个解决方案,而回滚机制,是当共识由于某些原因失败,而确保系统能够继续运作(保持功能)的一个先决条件。
图5: 使用并行BPQS逻辑将多种方案组合成一个实用后量子(PQ)方案的各种推荐设计。注意,如果底层方案需要额外的参数(如位掩码),这些应该和根公钥一起发布,类似图4所示 这三种描述到的方案,关于以下两个因素时,提供了不同程度的灵活性:
- 在密钥生成时间和签名大小之间选择一个平衡;
- 在稍后的时间里,决定是否允许选择底层算法;
例如,选项B需要生成两个PQ密钥,以形成待公告的组合公钥,同时选项A实际上是一个BPQS-EXT,它会被用于签署“即将到来”的PQ方案。沿着同样的路线,选项C是组合了A和B,但是左PQ方案不需要通过A-priori(先验)算法选择和计算。
注意,我们甚至还可以把两个不同的有状态的或无状态的方案结合起来,例如,如果出于兼容性需要,在两个不同的区块链中使用相同的密钥时,一个支持原有的SPHINCS-256 [23] 方案,而另一个则支持它的变体(或者其标准化版本)。
六、 实验结果
本节内容,将基于广泛的实验,展示BPQS方案的性能分析,并和一系列最先进的签名方案进行对比。选择这种对比方式,是因为它非常流行于今天的PKI和区块链社区。我们的实验结果,基于了一个可用BPQS签名方案的原型实现 [46],其中包括了如何重现基准测试的细节。
我们所选用的系统规格,包括八核的英特尔酷睿i7-7700HQ处理器(2.80GHz),15.5GB的内存,而系统运行的环境为 Linux 4.13.0-38以及JRE 1.8.0_161。关于实施方案,标准JCE已经用于哈希函数调用,而用于其他方案的实现,则分别基于BouncyCastle (ECDSA,RSA, SPHINCS-256) [47]以及 i2p (EdDSA) [48]库。
性能比较
表2 比较了各种签名方案的性能,包括使用SHA256和SHA384作为底层哈希函数的BPQS签名方案(w = 4和w = 16这两种情况)。报告结果的平均运行时间,以毫秒为单位。我们选择一个消息列表,而不是选择单个或少量信息的主要原因,是为了避免签名及验证操作当中可能出现的任何偏见现象。
表2:密钥对生成时间(单位:ms),签名和验证第一条消息的时间(单位:ms)。
需要强调的是,目前我们实施的BPQS方案是没有对并行处理进行优化的,它也不会缓存WOTS哈希迭代的中间结果。而缓存密钥秘密可大幅加快签名的处理速度,这已是公认的[33] 。在实践过程当中,因为BPQS签名方案最好是用于仅签名一次或几次的应用,因此OTS密钥的路径和数量相对较小,并且很容易放入内存当中。如果所有完整的WOTS结构,在密钥生成期间存入了内存当中,则签名无非就是一些内存查找,它不会涉及运行任何哈希操作,这就排除了前面所需的消息哈希。
即使没有实现并行化或缓存,BPQS签名方案和经典及后量子(PQ)数字签名算法的表现都是比较靠近的。需要强调的是,最简单的BPQS形式(BPQS-EXT),已被用于上述比较,其中会生成两个WOTS系列密钥,其中一个是签署第一则消息,另一个密钥则负责签署回滚操作。我们希望,一个区块链密钥的平均使用次数为1,而额外的签名只有在罕见和特殊的情况下才会进行,因此我们的比较也集中于第一次签名操作。在实践当中,我们期望区块链钱包都能够实现缓存和并行化,以进一步提升性能。
关于签名大小,所有BPQS模式,在前(log2(h) − 1) 次签名的表现都要优于XMSS签名方案,BPQS签名大小随密钥被重用次数而线性增长,因此签名输出的长度是动态的。它开始会很小,但会随着签名数的增长而增长。参数应该在初始密钥生成成本和签名大小之间进行权衡。在最好的情况下,签名的大小会随每个额外签名的一次哈希输出大小的增长而增长,而最坏的情况,则是随一次WOTS [19]的大小而变化。
图6: 不同模式BPQS和XMSS [5]签名方案支持32个OTS密钥的签名大小对比。所有方案的签名输出为 |W OT S| + x |H|,其中x是完全签名路径所需的额外哈希数。在这个图表当中,X轴代表签名的数量,而y轴代表x; 在大多数BPQS模式中,第一次签名输出的大小为 |W OT S| + |H|,而对XMSS而言,它的签名输出大小为| W OT S | + h×| H |,其中h是所用默克尔树的高度。当最为常用之一的WOTS(w = 16)被用作底层OTS方案时,则每个WOTS的大小为 |W OT S|,这就等于67 × |H|,其中 |H|是底层哈希函数的摘要大小(例如对于SHA256而言,就等于256位)。图6描绘了对于以下方案,每个额外签名的签名大小:
- BPQS-FEW (图2左侧),其中 h = 32;
- XMSS [5],h = 5,其中h代表树高;
- BPQS-VERS1 (图4),回滚到XMSS,高度h均为5;
- BPQS-GEN-B (图 5 B),右侧是BPQS-FEW,左侧是XMSS,俩者高度都为5;
七、结论及未来的工作
在这篇论文当中,我们介绍了BPQS签名方案及其扩展方案,以支持 {一次性和少次性}优化后量子(PQ)签名方案。我们还提出了区块链和分布式账本技术即将面临的安全挑战,然后解释了为什么我们不建议将纯OTS方案作为抗量子计算的替代品。如上所述, BPQS较传统的非量子签名方案(例如RSA、ECDSA以及EdDSA)会更具一些优势,它可以提供更可靠的量子安全性,这是因为它的加密哈希函数会更安全。
其中,BPQS协议的主要特征包括:
1、更短的签名、更快的密钥生成,当签名只进行一次或少数次数时,其签名和验证时间会比XMSS [5]和SPHINCS[23] 系列后量子(PQ)协议也会更短,而在区块链系统当中,这样做也可以实现更好的匿名性; 2、它在计算上与非量子方案相当。人们可以利用易于应用的多哈希链WOTS并行化和缓存,以提供几乎即时的签名和更快的验证; 3、其可扩展性属性,允许多次签名,它也可以很容易地进行定制,如果需要的话,它也可以回滚到另一种多次签名方案; 4、将其应用于区块链和分布式账本应用时,它可以通过引用先前的交易(其中相同的密钥会被重用),从而利用底层链或图结构的优势。这可能意味着,每个新的BPQS签名,只需要一次OTS方案的努力,因为其余到根的签名路径已经在账本当中了,因此可省略它们; 5、它可被用作一个构建块,用于实施新颖的PQ方案,例如同时的“有状态和无状态”方案,其可能会使集群环境受益,当共识消失时,其中的节点可回滚到无状态方案;另外,这样的方案可以用于向前和向后兼容的目的,或者当要求在两个独立和不兼容的区块链中重用一个密钥时;
这种原始BPQS协议的主要缺点在于,其签名输出大小是会随签名数量线性增长的。但是,我们可使用一种组合PQ方案或利用区块链应用当中现有的图形结构来减轻这种影响。总而言之,BPQS存在的可定制、缓存以及可扩展性属性,使其成为区块链理想的候选签名方案,它可以作为无状态、有状态以及其他PQ方案之间的一个桥梁协议。
论文引用
[1] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring”, 35th FOCS, pp. 124-134, 1994.
[2] J. Proos, and C. Zalka, “Shor’s discrete logarithm quantum algorithm for elliptic curves”, Quantum Information & Computation, v.3 i.4, 2003.
[3] M. Mosca, “Cybersecurity in an era with quantum computers: will we be ready?”, QCrypt, 2015.
[4] “The Quantum Countdown. Quantum Computing And The Future Of Smart Ledger Encryption”, Long Finance, http://longfinance.net/DF/ Quantum_Countdown.pdf, February 2018.
[5] J. Buchmann, E. Dahmen, and A. Hülsing, “XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions”, PQCrypto 2011: Post-Quantum Cryptography, pp. 117-129, 2011.
[6] J. Kelly, “A Preview of Bristlecone, Google’s New Quantum Processor,” Google Research Blog, https://research.googleblog.com/2018/03/apreview-of-bristlecone-googles-new.html, March 2018.
[7] D-Wave, “Temporal Defense Systems Purchases the First DWave 2000Q Quantum Computer”, D-Wave Press Release, https://www.dwavesys.com/press-releases/temporal-defense-systemspurchases-first-d-wave-2000q-quantum-computer, January 2017.
[8] T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, “Defining and Detecting Quantum Speedup”, Science vol. 345, issue 6195, pp. 420-424, July 2014.
[9] L. K. Grover, “A fast quantum mechanical algorithm for database search”, STOC, 1996.
[10] R. Anderson, and R. Brady, “Why quantum computing is hard-and quantum cryptography is not provably secure”, arXiv:1301.7351, 2013.
[11] “CECPQ1 post-quantum cipher suite,” Wikipedia article, https://en. wikipedia.org/wiki/CECPQ1, 2016.
[12] “The Post-Quantum PKI Test server”, http://test-pqpki.com/, 2018.
[13] L. Chen, S. Jordan, Y-K. Liu, D. Moody, R. Peralta, R. Perlner, and D. Smith-Tone, “NISTIR 8105 Report on Post-Quantum Cryptography”, NIST, 2016.
[14] NIST, “Post-Quantum Cryptography Standardization”, https: //csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-QuantumCryptography-Standardization, 2017.
[15] “Quantum Safe Cryptography and Security – An introduction, benefits, enablers and challenges”, ETSI, http://www.etsi.org/images/files/ ETSIWhitePapers/QuantumSafeWhitepaper.pdf, 2015.
[16] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity”, IACR Cryptology ePrint Archive: Report 2018/046, 2018.
[17] T. Ruffing, P. Moreno-Sanchez, and A. Kate, “CoinShuffle: Practical Decentralized Coin Mixing for Bitcoin”, ESORICS, 2014.
[18] P. Waterland, “The QRL Whitepaper”, https://theqrl.org/whitepaper/ QRL_whitepaper.pdf, 2011.
[19] A. Hülsing, “W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes”, IACR Cryptology ePrint Archive: Report 2017/965, 2017.
[20] S. Popov, “The Tangle”, https://iota.org/IOTA_Whitepaper.pdf, 2017.
[21] “How bad is reusing an address?”, IOTA forum, https://forum.iota.org/ t/how-bad-is-reusing-an-address/1277, 2017.
[22] R. G. Brown, J. Carlyle, I. Grigg, and M. Hearn, “Corda: An Introduction”, https://docs.corda.net/_static/corda-introductory-whitepaper.pdf, 2016.
[23] D. J. Bernstein, D. Hopwood, A. Hülsing, T. Lange, R. Niederhagen, L. Papachristodoulou, M. Schneider, P. Schwabe, and Z. Wilcox-O’Hearn, “SPHINCS: practical stateless hash-based signatures”, EUROCRYPT 2015, pp. 368-397, 2015.
[24] L. Lamport, “Constructing digital signatures from a one-way function”, Technical Report CSL98, SRI International, 1979.
[25] R. C. Merkle, “A Digital Signature Based on a Conventional Encryption Function”, CRYPTO 1987 pp. 369-378, 1987.
[26] D. Bleichenbacher, and U. Maurer, “On the efficiency of One-Time Digital Signatures”, ASIACRYPT, 1996.
[27] A. Hülsing, J. Rijneveld, and F. Song, “Mitigating Multi-Target Attacks in Hash-based Signatures”, PKC 2016 pp. 387-416, 2016.
[28] A. Perrig, “The BiBa one-time signature and broadcast authentication protocol”, 8th ACM Conference on Computer and Communication Security, pp. 28-37, 2001.
[29] L. Reyzin, and N. Reyzin, “Better than BiBa: Short One-time Signatures with Fast Signing and Verifying”, ACISP 2002, pp. 144-153, 2002 .
[30] J.Buchmann, E. Dahmen, E. Klintsevich, K. Okeya, and C. Vuillaume. “Merkle Signatures with Virtually Unlimited Signature Capacity”, ACNS, 2007.
[31] P. Kampanakis, and S. Fluhrer, “LMS vs XMSS: Comparion of two Hash-Based Signature Standards”, IACR Cryptology ePrint Archive: Report 2017/349, 2017.
[32] D. J. Bernstein, C. Dobraunig, M. Eichlseder, S. Fluhrer, S-L. Gazdag, A. Hülsing, P. Kampanakis, S. Kölbl,
[33] J-P. Aumasson, and G. Endignoux, “Improving Stateless Hash-Based Signatures”, IACR Cryptology ePrint Archive: Report 2017/933, 2017.
[34] S. Gueron, and N. Mouha “SPHINCS-Simpira: Fast Stateless Hashbased Signatures with Post-quantum Security”, IACR Cryptology ePrint Archive: Report 2017/645, 2017.
[35] S. Kölbl, M. Lauridsen, F. Mendel, and C. Rechberger, “Haraka v2 – Efficient Short-Input Hashing for Post-Quantum Applications”, IACR Cryptology ePrint Archive: Report 2016/098, 2016.
[36] Federal Information Processing Standards Publication 180-4, “Secure Hash Standard (SHS)”, Information Technology Laboratory, National Institute of Standards and Technology, March 2012.
[37] G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, “The KECCAK SHA-3 submission, Version 3”, 2011.
[38] M. Amy, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent, J. Schanck, “Estimating the Cost of Generic Quantum Pre-image Attacks on SHA-2 and SHA-3”, IACR Cryptology ePrint Archive: Report 2016/992, 2016.
[39] D. J. Bernstein, “Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?”, SHARCS 2009, 2009.
[40] “Measurements of hash functions, indexed by machine“, eBACS: ENCRYPT Benchmarking of Cryptographic Systems, http://bench.cr.yp.to/ results-hash.html, accessed: 21 February 2018.
[41] M-J. Saarinen, and J-P. Aumasson, “The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC): IETF RFC 7693.”, Internet Engineering Task Force. DOI: 10.17487/RFC7693, 2015.
[42] “IOTA ERROR: PRIVATE KEY REUSE DETECTED“, IOTA github, https://github.com/iotaledger/wallet/issues/928, 2018.
[43] C. Cachin, “Architecture of the Hyperledger Blockchain Fabric”, https: //www.zurich.ibm.com/dccl/papers/cachin_dccl.pdf, 2016.
[44] A. Hülsing, S-L. Gazdag, D. Butin, and J. Buchmann, “Hash-based Signatures: An Outline for a New Standard”, NIST Workshop on Cybersecurity in a Post-Quantum World, 2015.
[45] D. McGrew, and M. Curcio. “Hash-Based Signatures”, https:// datatracker.ietf.org/doc/draft-mcgrew-hash-sigs, accessed: April 2018.
[46] “BPQS library”, https://github.com/corda/bpqs, accessed: April 2018.
[47] “Bouncy Castle Crypto APIs”, v2.1.1, release: 1.59, 2017.
[48] “EdDSA-Java”, v0.2.0, https://github.com/str4d/ed25519-java, 2018.
以上所述就是小编给大家介绍的《学术向丨量子计算与区块链抗量子算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 量子计算能否攻克区块链?研究者:加密技术应向抗量子方向转型
- 区块链密码学如何对抗量子计算攻击?
- 程序员世界里的区块链、量子计算机和人工智能
- [量子计算]量子搜索Grover算法
- 从基础量子位到当下火热的量子计算机,一文助你入门量子计算
- 为什么抵抗量子计算需要量子密钥分发
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据结构C++语言描述
William Ford,William Topp / 刘卫东 沈官林 / 清华大学出版社 / 1999-09-01 / 58.00
一起来看看 《数据结构C++语言描述》 这本书的介绍吧!