TREE:?DAOrayaki：基于哈希的后量子数字签名是如何工作的？（一）-ODAILY_BITG

基于哈希的数字签名方案是后量子数字签名的一个类别。与目前用于验证区块链交易的数字签名方案不同，哈希函数为量子计算机提供的可利用结构要少得多，而且广泛认为它是量子安全的。

目前区块链基础设施上广泛使用的数字签名，如BLS和ECDSA，都是基于离散对数问题。

对于那些不熟悉数字签名的人来说，一个签名方案由四部分组成：系统生成，密钥生成，签名生成，以及签名验证。

例如，在ECDSA中，公钥Pk是通过椭圆曲线群上的生成点G来生成的，私钥Sk满足Pk＝Sk*G。给定Pk，利用经典算法很难找到Sk。

BLS签名方案是在配对群

上构建的。公钥/密钥对满足

量子算法善于寻找某些函数的周期性，它能发现经典难题的特殊结构，如因式分解和离散对数。当拥有数千个逻辑量子位的量子计算机出现时，BLS、ECDSA和其他依靠因式分解和离散对数问题的签名方案将不再安全。

例如，求一个数N=p*q的素因子可以简化为

求一个函数的周期。其中c是N的互素数。一旦找到周期，那么可以通过计算、

和找到两个互素因子。使用著名的辗转相除法可以很快找到最大公除数，它可以在经典的计算机上运行。反之，在经典计算机上很难找到D(x)的周期，但QPU可以在多项式时间内完成。

尽管当今的量子计算机只有几百个噪声的物理量子位，但量子计算机的建造者确实拥有大量的路线图来实现大规模的量子计算机。像IBM和RigettiComputing这样的超导量子计算机制造商正在向1000个物理量子位的量子计算机迈进，并使用可叠加的模块以获得更多数量的逻辑量子位。除此之外，在可预见的未来，还有其他几种方法可以带来有意义的量子计算系统，包括离子阱、中性原子和基于测量的量子计算。

但是，到目前为止，还没有发现有效的量子算法来破解哈希函数，而量子计算机只是将生日攻击速度提高到

而在经典计算机上的生日攻击速度为

现在让我们来看看如何使用哈希函数来构建数字签名，以及如何处理基于哈希的量子安全签名。

一次性签名方案

首个基于哈希的签名是于1979年首次推出的Lamport签名。一个Lamport签名密钥只能安全地签署一条信息，因此这是一个一次性签名方案。该签名方案的工作原理如下：

对于每条信息，签名者需要准备两组密钥对。

PKs是通过哈希SKs计算的。假设我们使用256位的加密哈希函数来产生消息摘要，每组密钥对由256个密钥和公钥组成。总的来说，我们需要准备512个密钥和512个公钥来签署任何一条消息。

要对一个消息签名，首先将消息散列成一个256位的随机数；然后，根据散列数的位值，相应地选择SK。

请注意，我们将始终对消息h(m)的摘要进行签名，而不是对任意长度的消息进行签名。为了简化标记，我们在本文的剩余部分将使用m代替h(m)。当你看到m，即表示着h(m)。

图片注释：签名是

和消息本身。

为了验证签名，首先计算H(m)，然后根据签名计算

,验证PK是否确实是来自SKs散列的结果，并且验证索引是否正确。

在对任何消息进行签名之后，该过程都会公开一半的密钥。因此密钥对只能使用一次，否则攻击者将能够使用公开的密钥来验证消息。

使用MerkleTrees管理OTS密钥

从21世纪加密用户的视角来看，Lamport签名方案乍一看可能很奇怪、很混乱。写下一次私钥或助记词可能就已经给人带来压力和烦恼，如果私钥只能签署一份信息，而每份消息都要共享不同的公钥，这不让人抓狂吗？

事实证明，如果我们能够适当地引入管理密钥的机制和工具，OTS签名方案也不是那么糟糕。

因为LamportOTS和WinternitzOTS一次只能签署一条消息，如果需要签署多条消息，就必须有多个密钥。MerkleTree的签名方案是由RalphMerkle发明的，用于管理LamportOTS密钥。

其基本原理是使用MerkleTree的叶子来存储LamportOTS密钥。因为MerkleTree是二叉树，高度为h的MerkleTree有

的叶子。如果使用叶子来管理LamportOTS密钥的摘要，那么MerkleTree可以管理

的LamportOTS密钥对。

当签署消息时，需要从树上摘取一个之前从未使用过的Lamport密钥对。签名由叶子的索引、Lamport公钥、Lamport公钥摘要和该叶子的认证路径组成。

密钥对，从而将空间从

减少到O(1)。这意味着，安全地交换一个Merkle根就允许多个签名验证。

使用MerkleTree的结果是，每次签名都必须包括认证路径，这是一个更大空间，而且验证者要对O(h)计算更多的哈希值来验证每个签名。

WinternitzOTS

LamportOTS的另一个问题是，Lamport公钥和Lamport签名太长。RobertWinternitz提供了一个改进的签名方案，大大减少了签名的大小。

WinternitzOTS不是为每一条消息准备私钥和公钥对，而是将哈希的消息分成几块。如果一个信息被分成N个块，并且每个块有1个比特，那么我们就得到了lenth(m)=N*L。我们将在本文中使用相同的$l,N&符号，以便于阅读。

假设我们仍然在信息上使用256位哈希函数，并获得信息的256位摘要。在这种情况下，N*L=256

使用上面的例子，m被分割成64个块，每个块有4位。所以，WOTS只需要准备64个私有密钥sk0，…，sk64。公钥是通过对每个私钥上应用

次哈希函数来计算的。

一个WOTS签名的生成方法如下。

1、计算消息摘要中每个块的十进制值。例如，第一块的十进制值是5。

2、通过将相应的私钥哈希运算计算第

i个区块的签名。在上面的示例中，sk0将被哈希运算次

3、对N个块应用和并生成签名

图片注释：每个公钥是通过对相应的私钥哈希运算

次来获得的。

为了验证签名，验证者将首先对信息进行哈希运算，得到一个256位的摘要m。然后验证者将m分成几块，得到每组的十进制值。

然后验证者将签名的每个值哈希运算

次，得到

。如果

与公钥集pk相同，则签名有效，否则签名被拒绝。

WOTS的折衷方案是在签名生成和验证中增加了更多的计算量。因此，WOTS的签名将明显比Lamport的签名小得多。

值得注意的是，WOTS仍然是一个一次性的签名方案，因为一旦使用了密钥对，只要块的十进制值小于原始值，攻击者就可以为每个块生成有效消息。因此，多次使用WOTS根本不安全。

WOTS+

WOTS+为WOTS增加了随机性。它首先向公钥集

元素匹配pk，则该签名有效，否则拒绝签名。

尽管WOTS和WOTS的一些变体使用简单的哈希链，但它们的迭代方法也很常见和简单。然而，WOTS+有一些特殊的迭代模式，可以实现严密的安全性证明，而不需要使用的哈希函数族具有抗冲突性。

扩展的MerkleTree签名方案

因为WOTS+仍然是一个一次性签名方案，如果有多条消息需要签名，那么密钥管理就非常重要。

扩展的MerkleTree签名方案使用MerkleTree来管理WOTS+密钥，其方式类似于MSS使用MerkleTree来管理Lamport密钥。

我们已经知道MSS是如何使用Lamport密钥对的，所以让我们先看看顶层的MerkleTree。

图片注释：用颜色标记验证最终XMSS公钥的认证路径

在XMSS中，公钥是XMSSMerkle根。MerkleTree的每个叶子都是WOTS+公钥集的Merkle根。为了说明这一点，从上面“扩展”

我们将有一棵“子”MerkleTree连接到上面的叶

上。这棵树在文献中也称为“L-tree”。

图片注释：一个由L-tree管理的WOTS+密钥集。实际树高取决于WOTS+密钥集的大小。

位掩码用于L-tree。在每次将哈希函数应用于两个节点之前，两个底部值将使用相应的位掩码进行异或运算。L-tree的每一层都有两个位掩码值

它们将该层的左、右节点进行异或运算。因此，一棵高度为h的L-tree总共需要2h的位掩码。

图片注释：L-trees是如何计算的——在进入哈希函数之前，将一个值与一个位掩码进行异或运算。

现在沿着L-tree向下移动——L-tree的叶子是WOTS+公钥。每片叶子代表一个WOTS+公钥，该公钥是使用WOTS+中描述的私钥的哈希值链创建。

图片注释：L-trees是如何计算的——在进入哈希函数之前，将一个值与一个位掩码进行异或。

要对消息m签名，首先从XMSS树中选择一个由i索引的叶子，并确保该叶子以前从未被使用过。然后我们知道该叶子是WOTS+公钥集的一个Merkle根。WOTS+私钥可以用来对消息进行签名，并得到消息m的WOTS+签名

。XMSS签名

和使用i索引的WOTS+公钥，然后使用

的正确性。

使用XMSS，可以管理和验证多个WOTS+密钥。

拓展阅读

本文介绍的签名方案是基于哈希的签名方案的基本构建块。AndreasHülsing等人在该论文中对基于哈希的签名方案的算法特性进行了更深入的分析。

还有其他以前NIST推荐的签名方案和多树方差和多树XMSS）。NIST最近的第三轮后量子密码学标准化过程目前不推荐这些签名方案以及本文第一部分所介绍的签名方案。然而，了解这些签名方案的细节非常重要，因为更新的、通常更复杂的签名方案是根据这些算法思想设计的。

本文的第二部分将介绍基于哈希的签名方案的最新发展，包括SPHINCS/SPHINCS+，以及工程和开源软件的现状。

标签：WOTTREEERKBITGWOT币OctreeTERKBitGet官方网站app

火币APP下载热门资讯