1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Commented 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$
    – poncho
    Commented May 19, 2021 at 19:27
  • $\begingroup$ @poncho I still don't get it. To sign N messages, we still need N Lamport pub/priv key pairs. So what's the advantage as compared to using those N 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$
    – radix
    Commented Oct 1, 2023 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$
    – poncho
    Commented Oct 1, 2023 at 16:25

Your Answer

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

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