Winternitz一次性签名 | Codeboy's Blog

形式陈述

消息位决定在链上走多远

固定底数b≥2和消息位数t≥1，消息为 $a=(a_0,\ldots,a_{t-1})\in\{0,\ldots,b-1\}^t$ 。这里的“位”是b进制数字，不一定是一个二进制bit。校验和及其固定宽度为

C(a)=\sum_{i=0}^{t-1}(b-1-a_i),\qquad s=\lfloor\log_b(t(b-1))\rfloor+1.

将C按大端写成恰好s位，保留前导零，得到 $c_0,\ldots,c_{s-1}$ 。令完整数字向量 $d=(a_0,\ldots,a_{t-1},c_0,\ldots,c_{s-1})$ ，长度L=t+s。s足以容纳最大值t(b−1)，特别是最大值恰为b的幂时也不能少一位。

经典构造用一个公开函数 $f:X\to X$ 。记 $f^0(x)=x$ ， $f^{j+1}(x)=f(f^j(x))$ 。独立均匀选L个秘密 $x_i$ ，公钥为 $y_i=f^{b-1}(x_i)$ 。对消息a，签名与验证为

\sigma_i=f^{d_i}(x_i),\qquad f^{b-1-d_i}(\sigma_i)\stackrel{?}=y_i\quad(0\le i<L).

验证者从消息重新算完整校验和，而不信任签名附带的任意校验和。公开参数确定b、t、X的编码和项数；不合法数字、长度或摘要项一律拒绝。正确性由 $f^{b-1-d_i}(f^{d_i}(x_i))=f^{b-1}(x_i)$ 给出。

这里追求的是至多一次查询的新消息不可伪造。函数仅有普通单向性还不能自动支持后面的密码安全结论；迭代输出上的额外假设在“推论与应用”中单列。

直觉

Lamport每个二进制位置准备两份秘密；链签名则让一份秘密沿同一条链走0步、1步、直到b−1步，用停靠位置代表更多种数字。验证者接着往前走，能抵达公开终点就表示这一链坐标相容。

问题也来自“只能向前”：看到第1步的签名，任何人都能自己走到第2步。所以直接用消息数字作为停靠位置，会允许把所有数字一起增大。校验和把两头绑起来：消息数字增加，补数之和就减少，于是至少有一条校验链必须向后退。

四条链表示两位消息及两位校验和，旧向量1110改成2103时第三条链必须从1退到0；后退用红色标出 — 消息前进，至少一条校验链后退

例子与边界

b=4时完整走完四条链

取t=2、消息a=[1,1]。校验和为 $(3-1)+(3-1)=4$ ，四进制固定两位写作[1,0]，故完整向量d=[1,1,1,0]。签名分别走1、1、1、0步，验证再走2、2、2、3步，每条都抵达第3步的公开终点。

若没有校验和，把第一项再算一次f，就能把[1,1]的签名变成[2,1]的签名。加入校验和后，新消息的C=3，必须写成[0,3]，新向量为[2,1,0,3]。攻击者能把第1链从1推到2，也能把第4链从0推到3，却需要把第3链从1退到0；现有材料没有直接提供这一步。

检查器使用 $f(x)=\mathrm{SHA256}(\mathtt{20}\Vert x)$ ，固定公开标签生成起点，实际验证原签名和无校验和的前推攻击，再确认保留旧校验项的伪造被拒绝。它枚举全部16条两位四进制消息之间的240个有序不同消息对，核对每对完整向量至少有一个坐标下降。它没有通过穷举32字节秘密来证明哈希无法反演。

校验和不是秘密，也不是另一个密码哈希

C完全公开，只承担“数字不能整体前进”的组合约束。若把真实C截成一位，本例4会变成0，向量的单调性证明便不再适用；若接受不同长度的前导零表示，链坐标也可能错位。消息长度和校验和宽度必须先固定。

本页用经典的同一个f反复迭代。标签20把它与本单元Lamport的10、列表树的00/01、稀疏树的02/03/04分开；标签不是秘密，也没有把SHA-256变成已证明安全的函数族。RFC8554的LM-OTS另外把密钥标识、链号、步号放进哈希，RFC8391的WOTS+还有地址、密钥与掩码。本页算法不冒称是它们的标准编码，不能直接拿到标准互操作系统中使用。

推论与应用

完整证明：不同消息不能全坐标前进

取不同消息a与a'。若某个消息坐标已满足 $a'_i<a_i$ ，完整向量当然已有下降。剩下只需考虑全部 $a'_i\ge a_i$ 的情况；因为消息不同，至少一项严格增大，因此 $C(a')<C(a)$ 。

两数都按同一s位b进制表示。如果a'的每个校验数字也都不小于a的相应数字，那么将各位乘以相同正权 $b^{s-1-j}$ 后相加，会得到 $C(a')\ge C(a)$ ，矛盾。因此至少一个校验坐标下降。两种情况合起来证明：任意不同消息的完整向量，都不可能仅从旧向量逐坐标增加得到。

这个引理排除了“只把已经看到的链点继续向前算”的伪造策略。它没有排除找到另一路前像、利用链合流或函数缺陷的其他攻击，因此不能单独代替密码安全归约。

密码结论需要什么更强条件

对d=b−1，迭代单向实验允许攻击者先选 $1\le j\le d$ ，再获得 $y=f^j(x)$ ，其中x均匀来自X；它必须输出z使 $f(z)=y$ 。要求每个高效攻击者的成功率可忽略，称为在d次迭代上单向。普通单向性只覆盖j=1，后续迭代的输入分布可能已改变，不能未经证明把j>1纳入。

在上述迭代单向条件、独立均匀链起点、b与L受多项式约束，以及完整数字向量满足刚证明的非支配性质时，经典Winternitz构造的一查询安全性由教材的迭代揭示归约给出。该归约处理攻击者看到部分链点后的反演，不只是对均匀起点调用一次普通OWF定义。若进一步用PRG压缩私钥或哈希压缩公钥，还须分别加入PRG安全与抗碰撞条件；本页未做这两项压缩。

因此这里有三层明确分工：链拼接给正确性，校验和给组合约束，迭代单向性支撑完整安全定理。下载的确定性公开测试起点不满足秘密独立采样的真实密钥模型，也不能用测试全绿替代第三层假设。

大小与计算的交换

若每个链点n字节，签名、公钥、原始私钥各Ln字节。生成公钥需L(b−1)次f；一次签名需 $\sum_i d_i$ 次，验证需 $\sum_i(b-1-d_i)$ 次，两者之和恰为L(b−1)。本例L=4，生成12次、签名3次、验证9次，签名128字节。小例并未比4bit Lamport的128字节更短，校验和开销在这里很显眼。

仅作长度账本：256bit按四bit一位拆成t=64个十六进制数字，最大校验和960，需要s=3，故L=67。若n=32，签名2144字节，公钥生成1005次f。这是表示与工作量计算，不是生产安全参数建议。增大底数通常缩短项数，却延长链，不能只报告签名变短。

终点任务：仍取b=4、t=2，把消息改成[0,3]，C=3，完整向量[0,3,0,3]，签名6次、验证6次。再取[3,3]，C=0，必须保留[0,0]两个校验位；解释为何不能省略这两条链。最后说出“普通单向”和“迭代单向”两个挑战分布的区别。

参考资料

Dan Boneh、Victor Shoup，作者教材v0.6，§14.3，Attack Game14.1、Definition14.5、Theorem14.4；§14.3.1、Lemma14.5给出非支配编码机制。完整密码归约援引该定理，本文展开的证明是校验和组合引理。
RFC 8554，§4.3–4.6与§9.3：LM-OTS链、校验和及其作用。该RFC的w表示每个数字的bit数，底数为 $2^w$ ；本文b直接表示底数。
RFC 8391，§3.1.2、§3.1.5–3.1.6：WOTS+地址化链和签验接口。本文固定f链不等于WOTS+。

形式陈述 ​

消息位决定在链上走多远 ​

b=4时完整走完四条链 ​

校验和不是秘密，也不是另一个密码哈希 ​

完整证明：不同消息不能全坐标前进 ​

密码结论需要什么更强条件 ​

大小与计算的交换 ​

反向链接