A one-time signature (OTS) authenticates exactly one message. Lamport’s construction uses only one-way functions: its private key contains random secrets, while its public key contains their hashes. section 14.2.1
A Lamport signature works in three small steps:
- Generate two random secrets for each message bit and hash them to form the public key. section 14.2.1
- For a 0 bit, reveal the first secret; for a 1 bit, reveal the second. section 14.2.1
- Verify by hashing each revealed secret and checking it against the corresponding public-key digest. section 14.2.1
The dangerous second signature
Reusing an OTS key pair exposes secrets chosen for different message bits. An attacker can mix those revealed secrets to forge another valid message, so used keys must be discarded or tracked. section 14.2.1
Figure 14.5 The Merkle signature scheme is a stateful hash-based algorithm that makes use of a Merkle tree to compress many OTS public keys into a smaller public key (the root hash). The larger the tree, the more signatures it can produce. Note that signatures now have the overhead of a membership proof, which is a number of neighbor nodes that allow one to verify that a signature’s associated OTS is part of the tree.
A Merkle tree compresses many OTS public keys into one root-hash public key, while each signature carries a membership proof and requires state tracking. section 14.2.3
