为比特币的量子抗性研究基于哈希函数的签名方案（二）

作者：conduition

来源： https://conduition.io/cryptography/quantum-hbs/

前篇见此处

Lamport 签名

假定我们希望使用哈希函数 $H(x)$ 来签名一个比特 —— 其值为 $0$ 或 $1$ —— 的信息。

我们生成两个长度都为 $n$ 的随机值原像：

$$ p_0 \leftarrow {0,1}^n $$ $$ p_1 \leftarrow {0,1}^n $$

这个元组 $(p_0, p_1)$ 就是一个 一次性的 私钥。

我们的公钥就是这个元组：$(P_0, P_1) = (H(p_0), H(p_1))$ 。我们可以把这个公钥交给任何人，随后再通过揭晓 $p_0$ 来签名比特值 $0$、揭晓 $p_1$ 来签名比特值 $1$， 这是安全的。任何知晓了公钥 $(P_0, P_1)$ 的人都可以通过运算 $H(p_b) = P_b$ 来验证 $p_b$ 是对比特值 $b$ 的签名

我们可以把这种方法推广到签名任意长度为 $m$ 比特的消息，只需生成更多原像即可 —— 为每一个比特生成一对原像。因此，我们的私钥就是：

$$ (p_0, p_1) : p_i \leftarrow {{0, 1}^n}^m $$

其中，每一个 $pi$ 都是一个包含了 $m$ 个随机原像 $p{(i,1)}, p{(i,2)}, \dots, p{(i,m)}$ 的数组。

（译者注：即 $p_0$ 就包含了用来签名每一个比特的数值 $0$ 的原像；而 $p_1$ 就包含了用来签名每一个比特的数值 $0$ 的原像。）

我们的公钥则是由各个原像的哈希值组成的。

$$ (P_0, P_1): Pi = (P{(i,1)}, P{(i,2)}, \dots, P{(i,m)}) = (H(p{(i,1)}), H(p{(i,2)}), \dots, H(p_{(i,m)})) $$

为了对一条消息（其比特值形式为 $b_1, b_2, \dots, b_m$）生成一个签名 $\sigma$ ，我们只需揭晓每一个比特值的对应原像：

$$ \sigma = (p_{(b1,1)}, p{(b2,2)}, \dots, p{(b_m,m)}) $$

要验证这个签名，只需为消息中的每一个比特 $1 \le i \le m$ 哈希签名中包含的原像、检查它与公钥一致，即：

$$ H(p_{(bi,i)}) = P{(b_i,i)} $$

属性

Lamport 签名是一种一次性的签名协议（缩写为 “OST”） —— 一旦签名人为给定的一个公钥揭晓一个签名，就再也不能用同一个公钥来签名另一条消息。要是重复签名了，这个签名人等于是拱手把伪造新签名的能力交给了观察到这多个签名的人。

举个例子，如果 $m=2$，而一个签名人为不同的两条消息 $0,1$ 和 $1,0$ 揭晓了两个签名，那就已经揭晓了其私钥 $(p_0, p_1)$ 中的所有（四个）原像。任何观察到这两个签名的人，都能用同一个公钥签名 $1,1$ 和 $0,0$，即使私钥的主人从未想过认可这些消息。

签名的长度以比特计是 $n \cdot m$，而公钥的长度是 $2nm$ 比特。

签名的过程很简单，因为只是揭晓秘密值。验证则要求使用 $H(x)$ 求值 $m$ 次。

修改

我们可以修改 Lamport 签名，从而优化密钥和签名的体积，代价则是一些计算时间。

确定性的密钥生成：不是随机取样出原像作为我们的私钥，而是从一个根秘密值 $r$ 触发，使用哈希函数 $H$ 来派生出它们：

$$ p_{(b,i)} = H(r,b,i) $$

这样一来，我们只需为每一个 Lamport 一次性签名密钥存储一个 $256$ 比特长的原像（而不是 $2m$ 个原像）。但我们需要计算 $4m$ 次哈希函数才能派生出我们的公钥，而且，要签名一条长为 $m$ 个比特的消息时，必须计算 $m$ 次哈希函数。

紧凑的公钥：我们可以将公钥的体积从 $2nm$ 个比特缩减到 $n$ 个比特，办法就是用标准的 Lamport 公钥自身的哈希值来表示公钥。也即：

$$ P = H(P_0, P1) = H(P{(0,1)}\dots P{(0,m)}, P{(1,1)}\dots P_{(1,m)}) $$

然而，这样一来，我们也必须调整签名算法，不仅要提供 $m$ 个原像，还要提供 $m$ 个互补的哈希值；验证者能用这些原像和哈希值重新构造出公钥哈希值 $P$，才能验证我们是私钥主人并签名了这条消息。因此，签名将是：

$$ \sigma = (p_{(b1,1)}, P{(1-b0,1)})\dots(p{(bm,m)}, P{(1-b_m,m)}) $$

也即签名的体积倍增了，变成了 $2nm$ 比特，而公钥的体积则从 $2mn$ 比特缩减到了 $n$ 比特。

要验证签名 $\sigma$ 时，验证者逐个哈希 $m$ 个原像、补充哈希值（公钥元素）后再次哈希，如能重新派生出 $P$，则验证通过；否则验证不通过。

对比

下表展示了不同 Lamport 签名方案的 时间/空间 取舍的具体案例。在这些案例中，我设 $m=n=256$、使用众所周知的哈希函数 SHA256 得出了这些结果。所有的体积都以比特数衡量。

而在下面这张表格中，我以调用哈希函数 $H(x)$ 的次数来衡量不同 Lamport 签名方案的时间复杂度。

对比特币的适用性

我估计，“紧凑 Lamport 签名” 方法将是 Lamport 签名中最为实用的一种，因为其公钥的体积跟当前的 P2TR 公钥是一样大的（或者可能更小）。

然而，即使是最为节约空间的 Lamport 签名，使用最低程度可接受的安全程度（$m=n=160$），每一个签名也要占据至少 $6400$ 字节的见证数据空间（如果不压缩的话）。这比一个 Schnorr 签名大 $100$ 倍。

而且还有公钥复用的问题。Lamport 签名是一种 一次性 签名方案。假设有一种 “支付给 Lamport 公钥” 地址，比特币用户从一个这样的地址花费的时候，他们绝不能再次使用同一个地址，否则就会让观察者获得一部分伪造签名的能力。

经验丰富的用户不怎么会受影响，因为他们已经采用了最佳的习惯，就是每个地址都只使用一次（只用在一个 收款/支付 周期中）。但是，如我们前文已经提到的，大量的比特币用户要么从来不知道有这个建议，要么视若无睹。很难说服这些用户重复使用搭配 Lamport 签名的地址不仅仅是个隐私问题 —— 它可能会直接摧毁你的钱币的安全性。对于用于冷存储的硬件签名设备来说，如果它们依赖于一台基本可信任（semi-trusted）的主机将交易推送给它们签名，事情将变得格外艰难。

Lamport 签名是带状态的，也就是一个签名人需要知道（记得）自己是否用过一个私钥来签名某一条消息，从而判断再次签名是否安全。

Lamport 签名 不能 向后兼容比特币当前的共识协议，即使 Ethan Heilman 提出了一种异想天开的方案，利用 OP_SIZE，用 Lamport 方案来签名一个 ECDSA 签名的长度。这种方法是否安全，还在讨论之中。但即使使用这种有想象力的方法，这样的签名的体积也会使它无法用在 P2WSH 地址中。至少以我们当前的知识，需要一次软分叉来为比特币添加对 Lamport 签名的支持。

即使在这样的软分叉之后，已经暴露了公钥的现有地址依然无法抵御量子敌手。用户需要主动将钱币迁移到软分叉所启用的 “支付到 Lamport 公钥” 地址格式中。

Winternitz 一次性签名（WOTS）

Winternitz 签名依赖于来自一组秘密值原像的哈希链条。通过揭晓链条上的特定中间哈希值，签名人可以签名一条消息。

与 Lamport 方案相比，WOTS 负担了更高的计算开销，换来了更短的签名。我们来看看它是怎么工作的。

首先，我们先重新确定一些参数：

• 令 $m$ 是我们要签名的消息的长度（以比特数量计）。
• 令 $w=2^t$ 作为所谓的 “Winternitz 参数”（它决定了 计算时间/占用空间 的取舍）。
• 令 $t=\log_2 w$，我们要将消息切分成长度为 $t$ 的比特组。
• 令 $\ell_1=\lceil m/t \rceil$ ，就是以 $w=2^t$ 为基数来衡量的消息的长度（位数）
• 令 $\ell_2=\lfloor \log_2(\ell_1(w-1))/t \rfloor+1$，作为以 $w$ 为基数来衡量的校验和的长度（位数）
• $\ell=\ell_1+\ell_2$ ，就是以 $w$ 来衡量的消息以及校验和的整长

因为 WOTS 依赖于哈希链条，我们需要一种哈希链条函数 $H

• 原文链接： btcstudy.org/2026/03/04/...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～