Hash function + PRF ⇒ DS (XMSS)

Fully-black-box reduction · standard model · BDH11

Statement

XMSS is a stateful, forward-secure, many-time hash-based signature scheme; it is EUF-CMA-unforgeable if its hash function family is second-preimage resistant and its function family is a PRF — BDH11.

Sketch

Each message is signed under a fresh Winternitz one-time key, and a Merkle tree over the one-time verification keys authenticates them under one root public key. Each pair of child nodes is XORed with public bitmasks before hashing, which lets second-preimage resistance replace collision resistance.

Notes

• SPHINCS+ removes the state with a hypertree of XMSS-style subtrees and the few-time signature FORS at the leaves — BHK+19.