I know they are both hash-based and post-quantum secure, and that Lamport signatures can form the basis for a Merkle scheme, but what do you actually gain over standard Lamport signatures by doing this? To put it another way, since Merkle signatures make use of another one-time signature scheme, why would someone use Merkle signatures when they have a perfectly fine one-time signature already?
1 Answer
why would someone use Merkle signatures when they have a perfectly fine one-time signature already?
Because Merkle signatures are not one-time. Instead, you can use a private key to sign a number of messages. There is a finite limit, however that limit is potentially large.
-
$\begingroup$ Would I be correct in my understanding that Merkle trees are, in fact, how one would squeeze multiple signatures out of one (initial) Lamport key? $\endgroup$ May 19, 2021 at 19:25
-
$\begingroup$ @JamesTheAwesomeDude: certainly, they're one way, but not the only one. An alternative way (assuming that the receiver will get all the signatures) is chaining; we include the next public key in the one time signature (and send that next public key as well). $\endgroup$– ponchoMay 19, 2021 at 19:27
-
$\begingroup$ @poncho I still don't get it. To sign
N
messages, we still needN
Lamport pub/priv key pairs. So what's the advantage as compared to using thoseN
Lamport pub/priv key pairs right away? A difference is that we send the Lamport pub key in the signature, and we only share the root pub key from the beginning, but is that a crucial advantage? $\endgroup$– radixOct 1 at 13:43 -
1$\begingroup$ @radix: if we know the receiver will accurately receive every message, we can indeed send the next Lamport (or Winternitz) public key with the current signed message. However, it is sometimes the case that the verifier may receive only signed message #42, without having received message #41 (or, for that matter, any previous signed messages) $\endgroup$– ponchoOct 1 at 16:25