Chapter 19Hash-Based Signatures: One-Time and Few-Time

19.1Why this chapter matters#

The previous part built signatures on lattice problems. This part builds them on a completely different foundation – nothing but a cryptographic hash function. There is no number theory, no lattice, no algebraic structure for an attacker to exploit: if the hash is secure, so is the signature. That makes hash-based signatures the most conservative post-quantum option, and it is why NIST standardized one (SLH-DSA, FIPS 205) as a hedge against a future structural break in lattices.

Because the foundation is so different, we introduce it the same way we introduced lattices: from the ground up. This chapter builds the atomic pieces – one-time and few-time signatures – and the next assembles them into a many-time, stateless scheme with Merkle trees. Only then, in Chapter 21, do we turn to the FIPS 205 standard itself.

19.2Learning goals#

After reading this chapter, you should be able to:

state the three security properties a hash function must provide, and why Grover only mildly weakens them;
construct and verify a Lamport one-time signature, and explain why it is strictly one-time;
explain how Winternitz (WOTS⁺) trades hashing time for much shorter signatures;
describe the few-time signature FORS and how its security bound changes with the signature count.

19.3What a secure hash function guarantees#

Earlier chapters used hash functions such as SHAKE only as expanders – deterministic ways to stretch a short seed into a matrix or noise (Chapters 15–16). Here a hash is the sole source of security, so we state precisely what is assumed of \(H:\{0,1\}^*\to\{0,1\}^n\).

Definition 19.1 (Hash-function security). A cryptographic hash \(H\) is assumed to be

preimage resistant (one-way): given \(y\), it is hard to find any \(x\) with \(H(x)=y\);
second-preimage resistant: given \(x\), it is hard to find \(x'\neq x\) with \(H(x')=H(x)\);
collision resistant: it is hard to find any pair \(x\neq x'\) with \(H(x)=H(x')\).

That is the whole assumption. Because there is no hidden algebraic structure, there is no Shor-style break; the only quantum help is Grover’s search (Chapter 1), which cuts preimage resistance from \(n\) bits to about \(n/2\). Hash-based schemes simply use a larger output \(n\) (16, 24, or 32 bytes) to keep a comfortable margin. The threat that shatters RSA leaves hashing merely needing bigger parameters.

19.4The Lamport one-time signature#

The simplest possible hash-based signature, due to Lamport [1], already contains the key idea: reveal a hash preimage as proof.

To sign an \(m\)-bit message, the signer prepares, for each bit position, two secret random values – one to reveal if that bit is \(0\), one if it is \(1\) – and publishes their hashes. Signing a message reveals exactly one secret per position: the one matching the bit. A verifier hashes each revealed secret and checks it against the correct public value.

**Figure 19.1.** One position of a Lamport key. Each of the \(m\) message-bit positions has two secret values whose hashes are public. A signature reveals exactly one secret per position – the one matching the message bit – and the verifier confirms it hashes to the published value. The unrevealed secrets stay hidden by preimage resistance.

KeyGen:

1:for \(i=0,\dots,m-1\) and \(b\in\{0,1\}\), sample \(sk_{i,b}\gets\{0,1\}^n\) and set \(pk_{i,b}\gets H(sk_{i,b})\)

2:return secret key \((sk_{i,b})\), public key \((pk_{i,b})\)

Sign message \(M=(M_0,\dots,M_{m-1})\in\{0,1\}^m\):

3:return \(\sigma=(sk_{0,M_0},\ sk_{1,M_1},\ \dots,\ sk_{m-1,M_{m-1}})\)

Verify \((M,\sigma=(\sigma_0,\dots,\sigma_{m-1}))\):

4:return accept iff \(H(\sigma_i)=pk_{i,M_i}\) for every \(i\)

Algorithm 25. Lamport one-time signature

Remark 1.1 (Why it is strictly one-time). A single signature reveals one secret per position – the ones matching \(M\). To forge a different message \(M'\), an attacker would need \(sk_{i,M'_i}\) at each position where \(M'_i\neq M_i\), and those secrets are still protected by preimage resistance. But two signatures on different messages jointly expose both secrets at every differing position, after which any message can be forged. Hence a Lamport key is safe for exactly one signature.

Lamport keys and signatures are large (each is \(2m\) or \(m\) hash values). The next construction keeps the one-time security but shrinks the signature dramatically.

19.5Winternitz: trading time for size (WOTS⁺)#

Instead of two independent secrets per bit, Winternitz uses one hash chain per base-\(w\) digit of the message. Starting from a secret \(sk\), repeated hashing produces a chain, and the public value is its end: \[sk \;\xrightarrow{H}\; H(sk) \;\xrightarrow{H}\; \cdots \;\xrightarrow{H}\; H^{w-1}(sk)=pk.\] To sign the digit \(m\), the signer reveals the intermediate point \(H^{m}(sk)\); the verifier hashes it the remaining \(w-1-m\) times and checks it reaches \(pk\).

**Figure 19.2.** One WOTS⁺ hash chain of length \(w\). The secret is the start, the public value is the end, and a signature reveals an intermediate point. A verifier hashes forward to check it reaches the public end. A full message digest is split into base-\(w\) digits, each signed by its own chain.

There is a catch a checksum must fix. Revealing \(H^m(sk)\) lets anyone hash forward to \(H^{m'}(sk)\) for any \(m'>m\), so an attacker could “advance” a digit to a larger value for free. WOTS⁺ appends a short checksum of the digits, itself signed by extra chains, arranged so that increasing any message digit forces decreasing some checksum digit – which would require moving a chain backward, i.e. inverting \(H\). The parameter \(w\) tunes a trade-off: larger \(w\) means fewer, longer chains (shorter signatures, more hashing), smaller \(w\) the reverse. Like Lamport, a WOTS⁺ key is safe for exactly one signature.

19.6FORS: a few-time signature#

One-time keys are unforgiving: a single reuse is catastrophic. The stateless scheme of the next chapters uses FORS (Forest Of Random Subsets), a few-time signature, inside a very large address space. This does not authorize key reuse; it makes the security analysis degrade more gradually under the tiny probability of an accidental address collision.

Definition 19.2 (FORS). FORS consists of \(k\) independent Merkle trees, each of height \(a\) (so each has \(2^a\) leaves, and each leaf hides a secret value). A message digest is split into \(k\) indices, one per tree; the signature reveals, for each tree, the secret at the selected leaf together with its authentication path to that tree’s root. The \(k\) roots are hashed together into a single FORS public key.

Because each tree reveals only the one leaf its index selects, the security bound degrades with the number of signatures and with any address collisions. SLH-DSA uses message randomization and a huge address space to make such collisions extremely unlikely. An implementation must never deliberately reuse a FORS or WOTS address; WOTS leaf reuse remains a serious event. (The Merkle trees FORS uses are the subject of the next chapter.)

19.7Summary#

This chapter built the atoms of hash-based signing:

security rests only on hash preimage/collision resistance, which Grover weakens merely to \(n/2\) bits;
Lamport signs once by revealing one preimage per message bit – simple but large;
WOTS⁺ replaces bit-pairs with hash chains plus a checksum, keeping one-time security at a fraction of the size;
FORS is a few-time signature whose security bound degrades with the number of signatures; address reuse is never an implementation strategy.

Every one of these keys is still usable only once (or a few times). The next chapter removes that limitation: a Merkle tree binds many one-time keys under a single public root, and a hypertree of such trees, addressed by hashing the message, yields a stateless many-time signature.

References

[1]

L. Lamport. Constructing digital signatures from a one-way function. Technical Report SRI-CSL-98, SRI International, 1979.