内容简介:以下为论文译文:作者: 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算法
- 从基础量子位到当下火热的量子计算机,一文助你入门量子计算
- 为什么抵抗量子计算需要量子密钥分发
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Head First HTML5 Programming
Eric Freeman、Elisabeth Robson / O'Reilly Media / 2011-10-18 / USD 49.99
What can HTML5 do for you? If you're a web developer looking to use this new version of HTML, you might be wondering how much has really changed. Head First HTML5 Programming introduces the key featur......一起来看看 《Head First HTML5 Programming》 这本书的介绍吧!