Winternitz One-Time Signature (WOTS)-编程实验室

本文章翻译自David Ireland首次发表于Winternitz One-Time Signature (WOTS)的原创文章, 强烈推荐有一定英文基础的小伙伴阅读原文。

Winternitz 一次性签名（WOTS）由 Winternitz 于 1979 年提出，稍早于 Lamport 论文的发表。该方案由 Merkle 描述 [MER79]。

拥有一个私钥x xx，对x xx重复应用哈希函数H HH共w ww次，即构成公钥，例如p k = H w ( x ) pk = H^{w}(x)pk=Hw(x)，其中w = 16 w=16w=16。
- 其中H w = H ( H ( H ( ⋯ ( H ( x ) ) ) ) H^w = H(H(H(\cdots(H(x))))Hw=H(H(H(⋯(H(x))))表示H HH被应用了w ww次。我们称此为哈希链 (hash chain)。
这样我们就可以用单个密钥对log ⁡ 2 ( 16 ) = 4 \log_2(16) = 4log2(16)=4比特的信息做签名。
首先将待签名的消息摘要分割成 4 比特的块，每个 4 比特块可以理解为[ 0 , 15 ] [0,15][0,15]范围内的某个整数。
例如要签名 4 比特消息1001 10011001（十进制 9），签名结果就是H 9 ( x ) H^9(x)H9(x)。
验证时，计算H 7 ( H 9 ( x ) ) = H 16 ( x ) H^7(H^9(x)) = H^{16}(x)H7(H9(x))=H16(x)并检查其是否等于已发布的H 16 ( x ) H^{16}(x)H16(x)值。
更一般地，给定一个在[ 0 , w − 1 ] [0,w-1][0,w−1]范围内的消息整数m mm，H m ( x ) H^{m}(x)Hm(x)作为其签名。
- 验证时，证明H w − m ( H m ( x ) ) = H w ( x ) H^{w-m}(H^{m}(x)) = H^w(x)Hw−m(Hm(x))=Hw(x)。

因此，使用 SHA-256 且w = 16 w=16w=16的原始 Winternitz OTS 方案如下：

私钥为x 0 , x 1 , x 2 , … , x 63 x_0, x_1, x_2, \ldots, x_{63}x0,x1,x2,…,x63
公钥为H 16 ( x 0 ) , H 16 ( x 1 ) , H 16 ( x 2 ) , … , H 16 ( x 63 ) H^{16}(x_0), H^{16}(x_1), H^{16}(x_2), \ldots, H^{16}(x_{63})H16(x0),H16(x1),H16(x2),…,H16(x63)
计算待签名消息M MM的 256 比特摘要：m d = SHA-256 ( M ) md = \text{SHA-256}(M)md=SHA-256(M)
将 256 比特的m d mdmd分割成 64 个 4 比特块，并将每个块解释为[ 0 , 15 ] [0,15][0,15]范围内的索引整数m i m_imi
m d = m 0 , m 1 , … m i , … m 63 md = m_0, m_1, \ldots m_i, \ldots m_{63}md=m0,m1,…mi,…m63；0 ≤ m i < 16 0 \leq m_i < 160≤mi<16
对每个m i m_imi，H m i ( x ) H^{m_i}(x)Hmi(x)作为其签名

w = 16 w = 16w=16且消息摘要为 256 比特的示例：

w ww的值称为Winternitz 参数。
我们不必使用w = 16 w=16w=16，也可以使用其他方便的 2 的幂次，例如 4 或 256。
w ww通常从集合{ 4 , 16 , 256 } \{4,16,256\}{4,16,256}中选择，对应的比特长度log ⁡ 2 ( w ) \log_2(w)log2(w)分别为{ 2 , 4 , 8 } \{2,4,8\}{2,4,8}。
- 注意：有些作者用w ww表示比特数，此时整数范围为[ 0 , 2 w − 1 ] [0, 2^w-1][0,2w−1]。
选择w ww的值是签名长度与处理时间之间的权衡。该值对方案的安全性没有影响。

由于F 9 ( x ) F^9(x)F9(x)是公开的，攻击者可以计算出F 10 ( x ) F^{10}(x)F10(x)并声称被签名的 4 比特消息是 1010（十进制 10）而不是 1001。
更一般地，如果攻击者能找到每个索引值都大于原始值的消息摘要，他们就可以伪造新消息的签名。
为了解决这个问题，我们在签名前向消息摘要附加一个 checksum。
如果摘要长度为n nn，则 checksum 的长度通常为log ⁡ 2 ( n ) \log_2(n)log2(n)量级。

以下是 SLH-DSA 中使用的 checksum 计算方法。对于上述示例，len_1 = 64，checksum 长度为 12 比特。

// Compute checksum for msg of len_1 w-bit integerscsum=0;for(i=0;i<len_1;i++){csum=csum+w-1-msg[i];}

WOTS+ 是对 WOTS 的改进，旨在防止某些攻击 [WOTSPLUS]。

其核心思想是：在哈希链中，每次不再仅仅使用普通哈希函数H HH，而是从可调整的哈希函数族中选择，以确保了哈希函数族中各成员之间的域分离 (domain separation)。

可调整的哈希函数 (tweakable hash function)除了消息输入外，还接收公共参数 P 和以调整参数 T 形式呈现的上下文信息。P可以被视为函数密钥或索引（PUBLICKEY），T可以理解为一个临时参数（NONCE）。

F = H(PUBLICKEY || NONCE || msg[i])

在实际应用中，这仅仅意味着每次调用哈希函数时其输入都是不同的。

在 SLH-DSA 中，函数F定义为：

F(PK.seed, ADRS, X) = Hash(PK.seed || ADRS || X)

其中PK.seed是公共种子，ADRS是 SLH-DSA 虚拟树结构中的地址，X是输入字符串。

在原始WOTS 中，p k = H w ( x ) pk=H^w(x)pk=Hw(x)，我们可以递归定义链接函数C CC为：

C[i] = H(C[i-1]), C[0] = X

因此C [ w ] = H w ( x ) C[w] = H^w(x)C[w]=Hw(x)。每次迭代使用相同的H HH函数。

在 WOTS+ 中，链接函数C CC使用可调整的哈希函数F FF递归定义：

C[i] = F(PK.seed, ADRS[i], C[i-1]), C[0] = X

其中ADRS[i]包含计数器i ii。

域分离用于允许在不同的情境（域）中使用相同的哈希函数。通过添加每次不同的域分隔符（PK.seed||ADRS[i]），实际上相当于每次哈希msg时都在使用不同的哈希函数，从而确保即使msg[i]重复也能得到不同的结果。

Winternitz One-Time Signature (WOTS)