# Chaining one-time signatures

To introduce the notation for the question, consider a one-time signature algorithm:

• There are a private signing key $$sk$$ and a corresponding public key $$pk$$, generated by $$Gen(seed)$$.
• To sign a message, use $$sig = Sign(sk, m)$$, and verify the signature by $$Ver(pk, m, sig)$$.

The one-time signature works as usual, with one limitation: if more than one message is signed with the same $$sk$$, there is no assurance that an attacker cannot forge a signature of another message without knowing $$sk$$. There is much work to expand this “one-timeness” to “many-timeness”, where “many” still stays limited.

I wonder, why one cannot use a plain one-time signature mechanism to sign an unlimited sequence of messages $$m_1, m_2, ...$$, as follows.

• Assume I have $$sk_1$$ and the verifier has $$pk_1$$.
• To sign $$m_1$$,
• Generate $$(sk_2, pk_2) = Gen(seed_2)$$,
• Calculate $$h_1 = hash(m_1, pk_2)$$, $$sig_1=Sig(sk_1, h_1)$$.
• Send to the receiver $$m_1$$, $$pk_2$$ and $$sig_1$$.

The receiver uses $$Ver(pk_1, hash(m_1, pk_2), sig_1)$$ to verify both the message and the authenticity of the next signature verification key.

The new key can be used to sign the next message and so on. This method can be used, for example, to sign software updates, where the "messages" come in a natural sequence.

• this method was described in Katz and Lindell book. But you do need to include all previous public keys, and sign the sequence, and they described a better construction in the next section as well. – DiamondDuck Jul 14 '20 at 15:55
• @DiamondDuck, thank you for the reference. I think in some applications this construction is good enough. – uk-ny Jul 16 '20 at 13:08

• The list of the previous signatures (along with $sk_i$ and $h_i$ values, in my notation) is non-secret and unforgeable, it can be published somewhere. – uk-ny Jul 14 '20 at 14:12