Explainer · by Kyeson Blake Utley

Winternitz signatures, explained.

How a signature scheme built from nothing but a hash function works, why quantum computers don’t break it, and where it lives inside today’s post-quantum standards. Includes a live demo that runs in your browser.

The problem

Most digital signatures in use today, RSA, ECDSA and Ed25519, rely on factoring or discrete logarithms being hard. Shor’s algorithm solves both efficiently on a large enough quantum computer. When one exists, anyone could forge signatures on software updates, certificates and blockchain transactions protected by those schemes.

Hash-based signatures avoid that. Their security rests only on the hash function: it must be hard to invert and hard to find a second input with the same output. The best known quantum attack on hashes, Grover’s algorithm, gives only a square-root speed-up, so a 256-bit hash still leaves roughly 128 bits of security.

Start with Lamport

In 1979 Leslie Lamport described the first one-time signature. Pick two random secrets for every bit of the message hash, publish the hash of each secret as the public key, and sign by revealing one secret per bit. It works, but signatures are enormous: for a 256-bit hash you reveal 256 secrets of 32 bytes each.

Winternitz’s trick: hash chains

Ralph Merkle’s work from the same period describes an improvement he credited to Robert Winternitz. Instead of signing one bit at a time, sign several bits at once with a hash chain.

With the common parameter w = 16, each chain signs one base-16 digit (4 bits):

Key generation. Pick a random secret sk. Hash it 15 times: pk = H¹⁵(sk). Publish pk.
Signing a digit d. Reveal H^d(sk), the value d steps along the chain.
Verifying. Hash the revealed value another 15 − d times. If you land on pk, the signature is valid.

A SHA-256 message digest is 64 hex digits, so 64 chains sign the message. One chain per 4 bits instead of one secret per bit makes signatures about four times smaller than Lamport’s.

Why a checksum is needed

Hash functions only run forward. Anyone who sees H^d(sk) can compute H^d+1(sk), so an attacker could take your signature and claim you signed a message whose digits are all larger. Winternitz closes that hole with a checksum: add up 15 − d for every digit and sign that number too, with three more chains. Raising any message digit lowers the checksum, and lowering a checksum digit would require going backwards along a chain, which means inverting the hash.

That gives 67 chains in total. With 32-byte hashes the signature is 67 × 32 = 2,144 bytes.

Try it

Message to sign

Public key (SHA-256 of all 67 chain ends): generating…

Grey: secret · dim green: steps the signer hashed · bright green: the value revealed in the signature · outlined: public key. Sign a second, different message with the same key to see why it’s called one-time. Everything runs locally with your browser’s Web Crypto API.

One-time means one time

Each signature reveals a point on every chain. Sign two different messages with the same key and an attacker learns the lower of the two points on each chain, and can then forge signatures for any message whose digits are at least that high on every chain. Real systems must never reuse a Winternitz key.

From one-time to many-time

A key that signs once isn’t much use alone, so practical schemes combine many of them:

Scheme	Standard	How it uses Winternitz	State
WOTS+	Introduced by Andreas Hülsing, 2013	Adds random masks to each chain step, allowing a security proof with weaker assumptions on the hash	One-time
XMSS	RFC 8391 (2018), NIST SP 800-208	Many WOTS+ keys as leaves of a Merkle tree; the root is the public key	Stateful
LMS / HSS	RFC 8554 (2019), NIST SP 800-208	Merkle trees of Winternitz-style one-time keys (LM-OTS), optionally in a hierarchy	Stateful
SLH-DSA (SPHINCS+)	NIST FIPS 205 (2024)	A hypertree of WOTS+ keys plus few-time FORS signatures, chosen pseudo-randomly	Stateless

Stateful schemes (XMSS and LMS) have small, fast signatures but must remember which one-time keys have been used. Restoring a signer from a backup or cloning a virtual machine can silently reuse a key, which is exactly the forgery case above. They suit tightly controlled settings like firmware signing. Stateless SLH-DSA removes that risk at the cost of larger signatures (about 7.8 KB to 50 KB depending on the parameter set).

Where this matters now

NIST finalized its first post-quantum standards in August 2024: ML-KEM (FIPS 203) for key exchange, ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) for signatures. LMS and XMSS were approved earlier in NIST SP 800-208. Hash-based signatures are the conservative choice where a signature must stay trustworthy for decades: firmware and boot chains, code signing and long-lived roots of trust.

If you’re planning a migration and want help choosing between ML-DSA, SLH-DSA and stateful hash-based signatures, or making a stateful scheme safe in production, talk to us.