Lamport signature

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Lamport signatures in simple terms

What it is
- A Lamport signature is a digital signature method that uses pairs of secret values and their hashes. It is designed to be secure even against some future threats, and it is a one-time signature: each private key should be used to sign only one message.

How it works (the basic idea)
- Key generation:
- Choose a hash function (for example a 256-bit hash).
- Create 2k random secret values (for a 256-bit hash, that’s 512 secret numbers).
- Hash each secret value to form 512 public values. Do not share the secret values; share the public hashes.
- Signing a message:
- Hash the message to k bits (for 256-bit hash, you get 256 bits).
- For each position i from 1 to k, look at the i-th bit of the hash.
- If the bit is 0, take the first value from the i-th pair of secret numbers.
- If the bit is 1, take the second value from that pair.
- The collection of these k secret values is the signature.
- Verifying a signature:
- Hash the message to the same k-bit value.
- For each position i, determine which public hash should be matched (based on the message bit).
- Hash every number in the signature and check that it matches the corresponding public hash from the public key.
- If all k hashes match, the signature is valid.

Security notes
- The security rests on the one-way hash function: an attacker would have to invert the hash to forge a signature without the secret values.
- The private key must not be reused. Using the same secret values again weakens security.
- Before signing, no one else knows the private values; after signing, most of them are discarded, so forging future signatures becomes much harder.

Scaling to many messages
- Each Lamport private key signs only one message. To handle many messages, a Merkle tree of public keys can be used. You publish only the top hash of the tree, and for each new message you reveal a new public-key leaf and its corresponding signature. This lets you sign many messages with a single root public value, at the cost of slightly larger signatures and more verification work.

Variants and improvements (simplified)
- Original vs improved: The original approach uses exactly one number from each pair for a signature. The improved version adds flexibility (you may publish both, one, or neither from a pair) to reduce key sizes while maintaining security.
- Key size and speed: There are methods to shrink key sizes and speed up signing, such as using hash lists or other compression techniques. Some approaches also use a single seed and a pseudorandom number generator to produce all needed secret values.
- Post-quantum thinking: Lamport signatures are designed to be compatible with large hash outputs to stay secure even if quantum computers become practical. Using bigger hash sizes and careful design helps maintain security margins.

A quick history
- Lamport introduced this idea in 1979 (building on earlier work). It’s a simple, classic form of a digital signature that remains interesting for certain security needs, especially where post-quantum considerations and one-time signing are important.

Summary
- Lamport signatures offer a straightforward, hash-based one-time signing method. They’re secure as long as the private key is kept secret and not reused, and they can be extended to many messages with trees or other techniques. They emphasize that the signature’s security comes from the hash function, not from any traditional public-key math.