2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – DiamondDuck
    Jul 14, 2020 at 15:55
  • $\begingroup$ @DiamondDuck, thank you for the reference. I think in some applications this construction is good enough. $\endgroup$
    – uk-ny
    Jul 16, 2020 at 13:08

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Some people even consider the need for the signing method to update state to be inacceptable. $\endgroup$
    – SEJPM
    Jul 14, 2020 at 12:20
  • $\begingroup$ 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. $\endgroup$
    – uk-ny
    Jul 14, 2020 at 14:12
  • $\begingroup$ @uk-ny: signatures and signed messages (although you could modify the scheme so you'd need only publish their hashes). Still, it's not that convenient to have refer to the published site to be able to verify this signature; and it is certainly not that convenient to have to compute 1,000,000 previous signatures if you need to validate the 1,000,001th $\endgroup$
    – poncho
    Jul 14, 2020 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.