量子计算与区块链抗量子算法

巴比特 中字

五、为一次性密钥定制的区块链化后量子签名

大多数(如果不是所有的)少次哈希签名方案都使用了默克尔树(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签名方案有两个基本构建部分:

1.BPQS-FEW:其严格支持少次性签名,如图2所示(左侧);

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所示 这三种描述到的方案,关于以下两个因素时,提供了不同程度的灵活性:

1.在密钥生成时间和签名大小之间选择一个平衡;

2.在稍后的时间里,决定是否允许选择底层算法;

例如,选项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描绘了对于以下方案,每个额外签名的签名大小:

1.BPQS-FEW (图2左侧),其中 h = 32;

2.XMSS [5],h = 5,其中h代表树高;

3.BPQS-VERS1 (图4),回滚到XMSS,高度h均为5;

4.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方案之间的一个桥梁协议。

声明: 本文系OFweek根据授权转载自其它媒体或授权刊载,目的在于信息传递,并不代表本站赞同其观点和对其真实性负责,如有新闻稿件和图片作品的内容、版权以及其它问题的,请联系我们。
侵权投诉

下载OFweek,一手掌握高科技全行业资讯

还不是OFweek会员,马上注册
打开app,查看更多精彩资讯 >
  • 长按识别二维码
  • 进入OFweek阅读全文
长按图片进行保存