译者前言：量子计算领域的最新进展让很多人对经典密码学的前景感到担忧。例如，谷歌开发了一种具有72个量子位的量子计算芯片，距离破解经典密码学所需的数千个可用量子位不再那么遥远。有人估计，到2031年，RSA和ECC(椭圆加密)算法被破解的概率约为50%。比特币和以太坊等区块链使用的是经典密码学。虽然比特币使用双重SHA256算法，这使其比银行和支付宝使用的安全系统多了一道防线，但它仍然有各种各样的攻击载体。量子计算似乎正在成为区块链的达摩克利斯之剑，我们需要担心吗？

译者认为需要我们密切关注，但也不需要过于担心。在真正紧急的情况下，社区可以通过硬分叉的方式替换比特币等区块链使用的加密算法，区块链业界的一些研究人员也在不断研究相关的反量子加密算法。来自联盟链团队R3的研究团队，在分析相关攻击向量的同时，提出了一个反量子签名方案。从结果来看，

以下是论文翻译：

后区块链量子(PQ)签名

作者：康斯坦丁诺斯查尔基亚斯？詹姆斯布朗？迈克赫恩？汤米利勒哈根、伊戈尔日东？托马斯施罗特克(R3)

联系人：邮箱：konstantinos.chalkias@r3.com？james.brown@r3.com？mike@r3.com，汤米.利勒哈根@r3.com，Igor.nitto@r3.com，克托马斯。schroeter @ r3.com

摘要——受区块链架构和现有的基于Merkle树的签名方案的启发，我们提出了BPQS，一种可扩展的抗后量子(PQ)的数字签名方案，最适合区块链和分布式账本技术(DLT)。该协议的一个独特之处在于，它可以使用特殊的链或图像结构来降低密钥生成、签名和验证的成本以及签名的大小。与最近的其他改进相比，当一个密钥被合理数量的签名重用时，BPQS将优于现有的哈希算法，如果需要，它还支持回滚机制，可以允许无限数量的签名。我们提供了该协议的开源具体实现方案，并对其进行了基准测试。

本文相关术语：后量子加密、数字签名、分布式账本、区块链、Merkle树

一、引言

量子计算领域的最新进展及其对经典密码学的威胁引起了更多人对后量子(PQ)研究的兴趣。

更具体地说，由于Shor算法[1]，量子计算机可以很容易地在多项式时间内分解大整数因子，从而有效地破解RSA。Shor算法的激活可以解决离散对数问题，如今的数字签名(如DSA、ECDSA、EdDSA)使其失效[2]。

建造量子计算机的竞赛已经开始。像谷歌、微软、IBM、D-Wave、英特尔这样的公司已经处于领先地位。然而，到目前为止，我们还无法建造一台拥有数千个稳定量子位的计算机，可以让经典的公钥密码学过时。然而，这一领域已经取得了显著进展，一些乐观主义者预测，在未来10到20年内[3]和[4]，一台大型量子计算机可能能够破解非对称加密。破解公钥加密系统会带来很大的安全影响。几乎所有的东西都来自HTTPS、VPN和PKI，其中涉及到RSA或椭圆曲线加密算法(ECC)的安全性。区块链领域也将受到打击，它可能是受影响最大的领域之一，因为黑客可以从中获得经济激励，他们可以匿名访问区块链账户。

为了解决密钥泄露问题，PQ密码学开始兴起，它将保护我们免受量子霸权的冲击。我们提出的BPQS解决方案是基于XMSS方案的修改版本[5]。 它实际上使用单一的认证路径；因此，它是一条链，而不是一棵树。它只需要关注{一次性和少数几次}键，也就是说，它通常最适合区块链(因为我们希望保持匿名和最小化跟踪)。与现有方案相比，我们的方案在只需要签名一次或几次的情况下会有更好的性能。与一次性签名方案(OTS)不同，BPQS方案提供了回滚机制，可以方便地支持多重签名。据我们所知，这是第一个可以利用现有区块链或图形结构来降低签名成本的签名方案(即使我们计划多次签名)。这使得现有的多态签名方案对于区块链应用来说已经过时。此外，事实上，BPQS完全基于哈希函数，因此它的实现不需要特殊的数学理论，这使得它成为现有或新区块链应用程序的强大签名方案候选。

二、量子计算

在更高效计算的市场需求和解决以前不切实际问题的能力的推动下，量子计算从基础理论研究走向实用研究的进程正在快速推进。十年前，几乎没有实用量子计算机的证据。然而，2018年，谷歌推出了72量子位的新量子计算芯片Bristol Cone [6]，比IBM 2017年宣布的50量子位处理器提前了22量子位。我们还应该提到D-Wave公司，该公司最近宣布了2000量子位处理器[7]。但据报道，D波的量子加速分析值得商榷[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漏洞将威胁到这些书的完整性[16]。

这将是一个重大的安全风险，会导致网络被完全破解，大多数区块链使用公钥密码哈希生成的地址来缓解这种威胁。

这个额外的安全层意味着公钥在参与第一笔交易(即消费比特币)之前不会暴露在账本中。直到此时，才暴露出哈希接收方密钥(地址)，所以像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。战略性的资产双重支出会导致交易被拒绝。这种情况也可能是故意锁定，使等待的事务被拒绝。这种情况可能发生在意外支出的场景中。用同一个密钥签署一个重复的事务，会导致两个事务同时失败，而且会导致不好的后果，就是密钥被重用。

四、基于hash的后量子(PQ)数字签名

A .一次性签名(OTS)

基于hash的签名方案可以追溯到1979年，这要归功于Lamport OTS方案[24]。

Lamport方案背后的逻辑很清楚：签名者生成一个每个比特都需要签名的随机值对，并形成一对私钥。公钥由这些值的散列组成。 为了签署消息，签署者逐位读取消息并显示一个值。每个秘密对取决于比特值。然后，验证者可以验证所有秘密值的散列是否等于公钥中的相应散列。虽然Lamport OTS哈希计算被认为是快速的，但它的密钥和签名大小相对较大。例如，如果SHA256用作底层散列函数，则公钥由512个256位散列输出组成(每位1个散列对)，签名由256个秘密值组成(每个256位)。如果把密钥和签名数据加起来，需要占用24.5 kB。同样，如果使用SHA512算法，大约会占用98kb；

对原算法[19]、[25]、[26]的进一步增强可以显著减小密钥大小。目前，WOTS算法[19]及其变体被认为是最有效的密钥和签名压缩方法，而Bleichenbacher和Maurer [26]的图形方案试图在每个消息位的签名大小和哈希函数求值次数方面达到最佳效率。

作为一个评论，OTS方法的一个主要区别在于所需的安全假设是否针对反哈希函数，以及是否使用反哈希函数。目前，WOTS-T [27]已经在QROM模型中被证明是安全的，被认为是WOTS级数方案[19]最有希望的候选方案，因为只需要用一个额外的种子值与公钥一起计算所需的比特掩码，其安全性不会受到“生日悖论”的影响。它还引入了所有哈希关键函数调用，以防止多个目标进行第二次原始图像攻击。后者导致更短的公钥和散列输出大小。

B .不太频繁的多重签名

虽然将一次性签名方案转化为多重签名方案的方法有很多种[5]，[28]-[30]，但一种流行的方法是使用Merkle认证树。使用Merkel树，可以发布的签名总数在密钥生成时定义。这样做的主要优点是签名输出短，验证快，缺点是密钥生成时间相对较长，而且它们是有状态的。图1描绘了4度(最大)默克尔树签名方案。

图1:最多可以签署4条消息的默克尔树签名方案。如果我们用OTS1方案签名，深色节点表示所需的认证路径。

并且转向无状态的少签名方案需要额外的复杂性和更大的签名输出。HORS [29](及其扩展HORST [23])方案是最常用的多重无状态签名方案，如SPHINCS [23]。

多重哈希签名方案可以通过组合上述{一次及更少}的方案来构造，它们可以分为两类：有状态的(如XMSS，LMS)[31]和无状态的(如SPHINCS，SPHINCS，Gravity，Simpira，Haraka)[23]，[32]有状态的方案通常产生短签名，但是它们需要一种机制来维护状态(哪些路径/密钥已经被使用)。另一方面，无状态方案在顶部以中等大小的默克尔树或树层开始，而不是在底部使用OTS签名。他们使用不太常见的签名方案。后者允许它们随机选择索引，因此不需要跟踪路径状态。无状态方案的缺点是它们的签名大小。例如，在SPHINCS-256 [23]方案中，每个签名的大小将是41 kB。并不总是清楚

次要和多重散列签名方案。在文献中，次要签名方案通常指无状态方案，如芭比[28]，霍斯[29]和霍斯特[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：其严格蓑衣网小编2022支持少次性签名，如图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协议，蓑衣网小编2022其具有高度为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使用具有更大输出的蓑衣网小编2022哈希函数（例如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.