TransWikia.com

Chaining one-time signatures

Cryptography Asked by uk-ny on October 24, 2021

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.

One Answer

I am wondering, why I cannot use a plain one-time signature mechanism to sign an unlimited sequence of messages

You can; your method does exactly that. However, it assumes that the verifier sees all previous signatures before verifying the next - not all use cases can assume that.

Answered by poncho on October 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP