一、引言

量子计算领域的最新进展，及其对古典密码学的威胁，促发了更多人对后量子（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