Lamport一次性签名

公钥像每个位置上两把锁的验证样本。消息位是0，就交出这一位0侧的钥匙；消息位是1，就交出1侧的钥匙。别人能核对交出的钥匙，却不应因此学会同一位置另一侧的钥匙。

一条新消息至少改变一个位置。在那个位置，攻击者要打开一把此前没有拿到原像的锁。安全证明要把这句话变成具体反演算法，而不能仅说“哈希很难逆”。特别是对手看完公钥才选消息，归约仍须处理这种自适应选择。

四位消息1010 ​

把8份秘密写成下表，每列是同一消息位置：

签1010时公开 $x_{0,1},x_{1,0},x_{2,1},x_{3,0}$。若把消息改成1011，最后一项就需要 $x_{3,1}$ 的某个合法原像，而现有签名给的是0侧。

HASH-6检查器令 $f(x)=\mathrm{SHA}256(\mathtt{10}\Vert x)$，秘密项固定为32字节。它用公开标签生成可重复的教学数据，并列出完整公钥和签名。这些“秘密”人人可算，绝不是安全密钥；脚本检验的是算法、编码与反例，不是通过实验建立密码困难性。

签两条消息以后怎样伪造 ​

故意用同一私钥签0000和1111，攻击者就得到全部8份秘密。无需反演任何函数，它从两份签名取出 $x_{0,0},x_{1,1},x_{2,0},x_{3,1}$，拼成0101的签名。0101没有被请求过，却通过验证。检查器实际执行这项攻击。

更一般地，两条已签消息在d个位置不同，就暴露这d列的两侧，其他列只暴露一侧。仅靠选择这些已知原像，就能为 $2^d$ 条消息拼接签名。其中最多两条是原查询；d≥2时至少出现新的可拼消息。d=1的这类简单拼接只给原来的两条，不能由此宣称任何两次查询都必然立即产生新消息攻击；安全保证仍已超出一次查询的适用范围。

重复发送同一份已有签名不会额外暴露另一侧。对于本页确定性算法，再签同一条消息也返回同样内容；但一般有状态接口仍应把重新签名与重传已有签名区分开，避免上层把消息变化误判为同一次请求。

从伪造到反演的猜位归约 ​

先考虑对手确实查询一次的情况。归约者拿到单向挑战 $y=f(x)$，均匀猜一列I和一侧B，把挑战放进公钥的 $y_{I,B}$，其他 $2\ell -1$ 项正常生成。挑战像与真实随机原像的像同分布，因此整张公钥分布正确，而且隐藏的(I,B)不因这个嵌入泄露给对手。

查询消息m到来时，若 $m_I=B$，归约者不知道该原像而中止；否则它知道所有被请求原像，可以原样回答。若对手后来为 $m^{\ast }\ne m$ 给出有效签名，并且 $m_I^{\ast }=B\ne m_I$，输出 ${\sigma }_I^{\ast }$。验证等式保证它是y的一个原像；不要求与挑战者最初采样的x完全相同。

在一次成功的真实伪造记录中，设新旧消息不同的位置数为d≥1。共 $2\ell$ 种均匀猜测中，有d种命中“新位侧且旧位相反”，这些分支不会中止。嵌入挑战与普通公钥项分布一致，所以成功率至少为原伪造成功率的 $1/(2\ell )$。若对手不作查询，归约无需回答，猜中伪造所用一侧的概率为1/2，同样不劣于这个界。

因此，对任意该类伪造者A，存在高效反演者B满足

函数族单向且ℓ为多项式时，右侧可忽略。这是普通新消息不可伪造结论；没有由此证明同消息上的强不可伪造。f可以有多个原像，不能额外假设每条消息恰有一份可接受签名。

大小、预哈希与下一步 ​

若x、y均n字节，私钥与公钥各为2ℓn字节，签名ℓn字节。生成公钥需2ℓ次f，签名仅选择并复制ℓ项，验证需ℓ次f；签名的字节输出本身仍需时间。本例ℓ=4、n=32，公钥256字节、签名128字节。

签任意长文档时，常先用另一公开哈希G压成ℓ位。此时新文档可能产生同一摘要；必须把G的碰撞问题纳入证明，并固定文档编码、用途标签与消息域。本页主例直接签4位，不把“先哈希一下”隐藏在既有定理里。

终点任务：对0011与0101画出暴露的原像列，列出可拼出的四条消息0011、0001、0111、0101，指出新消息0001与0111。再解释为何把同一份公钥重新编号，或放进不同证书，并不会恢复已经泄漏的秘密。Merkle签名理路Merkle树签名与一次性索引Merkle signature scheme · Stateful Merkle signatures把独立一次性公钥装入认证树，以根作为长期验证锚点，并将不可回滚的索引消耗纳入安全模型和可复算故障轨迹。使用真正独立的一次性密钥，而不是给同一密钥换标签。