Lamport signatures: hash-based signing from scratch

A signature from one assumption

Every signature scheme you used before this course leans on number theory. RSA uses factoring; ECDSA and Ed25519 use elliptic-curve discrete logarithms. Shor's algorithm breaks both. Hash-based signatures need only one thing: a hash function that's hard to invert.

That's a comfortable assumption. Against a hash, the best known quantum attack is Grover's algorithm, a generic quadratic speedup that's hard to parallelize. There's no structure for Shor to grab. Leslie Lamport described the simplest such scheme in a 1979 SRI technical report, Constructing Digital Signatures from a One Way Function. It is still the clearest way in.

The scheme

We'll use SHA-256 throughout, so messages are signed via their 256-bit digest.

1. KeyGen. Generate 256 pairs of random 32-byte secrets: sk[i][0] and sk[i][1] for i = 0…255. The public key is their hashes: pk[i][b] = SHA-256(sk[i][b]).
2. Sign. Compute d = SHA-256(message). For each bit position i, reveal sk[i][d_i]: the secret matching that bit.
3. Verify. Recompute d. For each i, check SHA-256(sig[i]) == pk[i][d_i].

import hashlib, os
H = lambda x: hashlib.sha256(x).digest()
bits = lambda d: [(d[i // 8] >> (7 - i % 8)) & 1 for i in range(256)]

def keygen():
    sk = [[os.urandom(32), os.urandom(32)] for _ in range(256)]
    pk = [[H(a), H(b)] for a, b in sk]
    return sk, pk

def sign(sk, msg):
    return [sk[i][b] for i, b in enumerate(bits(H(msg)))]

def verify(pk, msg, sig):
    return all(H(s) == pk[i][b] for i, (s, b) in enumerate(zip(sig, bits(H(msg)))))

A tiny worked example

Shrink the digest to 4 bits to see the mechanics. Suppose the digest of your message is 1011. You reveal sk[0][1], sk[1][0], sk[2][1] and sk[3][1], and keep the other four secrets. The verifier hashes each revealed value and checks it against pk[0][1], pk[1][0], pk[2][1] and pk[3][1]. Change one bit of the message's digest and the verifier looks up a different public hash, one whose preimage you never revealed.

The cost profile is unusual. Key generation is 512 random values and 512 hashes; verification is 256 hashes. That is cheap computation. The expense is all in bytes.

Security for a single signature is intuitive. To forge a signature on a different message, you need at least one secret that was never revealed. Getting it means inverting SHA-256 on a public hash. The only alternative is finding a second message with exactly the same digest, a second preimage.

The sizes

A cheap trick for the public key

A 16 KB public key is awkward to publish, pin in firmware or put in a certificate. One standard move is to publish only H(pk), a single 32-byte hash of all 512 public values. The signer then sends the 256 public hashes for the unrevealed halves along with the signature. The verifier hashes the revealed secrets, combines them with the supplied hashes into the full public key, and checks that its hash matches the published 32 bytes. The public key shrinks to 32 bytes; the signature roughly doubles. Hold onto this idea of "commit with one hash, prove membership later." It's exactly what Merkle trees generalize.

Lamport is big and single-use. The next lesson fixes both problems. But first, let's see exactly what goes wrong when you reuse a key.

Signing twice

A one-time signature is exactly what it says on the tin. Here's the precise damage when you ignore the label.

After one signature, the attacker holds one secret per pair: the ones matching digest d(1). Now you sign a second message with digest d(2). Wherever the two digests differ, about 128 positions for random digests, the attacker now holds both secrets. Those positions are free: a forged digest can have either bit there. The other positions are still pinned to one value.

So to forge, the attacker needs a message whose digest matches the pinned bits. With c pinned positions, that takes about 2^c hash attempts. Each extra signature roughly halves the pinned positions:

And that's the gentle case, where the victim signs random-looking messages. If the attacker can choose what gets signed, or influence it, they can pick messages whose digests expose the bits they need, and the collapse comes faster. Reuse also hands the attacker leverage nobody can audit afterwards: there's no way to "un-reveal" a secret.

Sign a few messages and watch red pairs, where both halves are revealed, spread across the grid. Once the attacker's work estimate drops low enough, the forge button grinds through candidate messages with real SHA-256 until one fits. Then it assembles a signature purely from secrets you already published, and the verifier accepts it.

Why bother with something so clunky?

Because its security argument is about as clean as cryptography gets. If SHA-256 is preimage- and second-preimage-resistant, Lamport signatures are unforgeable for one use. No lattice estimates are involved, and no structured algebra for a future algorithm to exploit. That conservatism is why hash-based schemes are standardized for the long haul:

• LMS (RFC 8554) and XMSS (RFC 8391), approved in NIST SP 800-208, are stateful schemes built from Winternitz one-time signatures and Merkle trees. NSA's CNSA 2.0 lists them for software and firmware signing.
• SLH-DSA (FIPS 205, from SPHINCS+) is a stateless hash-based signature built from the same ingredients plus a few-time scheme, so there's no counter to manage. The price is signatures of roughly 8 to 50 kilobytes.

All of them are descendants of the 512 hashes you just generated. The rest of the family history is compression: make each one-time signature smaller (Winternitz), then make one public key cover many one-time keys (Merkle).

Questions

Get five of six right to mark the lesson complete. They also feed the final exam.

Sources

• Lamport, Constructing Digital Signatures from a One Way Function, SRI CSL-98 (1979)
• NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes
• RFC 8554: Leighton-Micali Hash-Based Signatures
• NIST FIPS 205: Stateless Hash-Based Digital Signature Standard

Drawn byKyeson Blake Utley

CourseQuantum Defense

Sheet15 of 18

PartIII · Engineer

Rev.18 Oct 2026

Sources4 cited

Found an error?Send a correction