XMSS

XMSS, short for eXtended Merkle Signature Scheme, is a hash-based digital signature scheme designed for post-quantum security. It builds signatures from a Merkle tree of Winternitz one-time signatures (WOTS+), providing strong cryptographic guarantees based on hash functions rather than classical number-theoretic problems.

The private key for XMSS encodes a secret seed and a tree structure that defines a set of one-time keys for the tree’s leaves. The public key comprises the root of the Merkle tree. Each leaf corresponds to a WOTS+ key pair, and the leaf’s authentication path to the root is used to verify the signature. Signatures therefore reveal a specific leaf’s WOTS+ signature plus the authentication path, enabling the verifier to reconstruct the root and confirm it matches the public key.

To sign a message, the signer uses the next unused leaf’s WOTS+ key to create a signature on the message and provides the authentication path from that leaf to the root. Verification uses the signature, the authentication path, and the public root to recompute the root; if it matches, the signature is valid. XMSS is stateful: reusing a leaf or its authentication path can compromise security, so careful state management is required.

XMSSMT, or XMSS Multi-Tree, extends the scheme by employing multiple Merkle trees to increase the total number of signatures and reduce per-signature state pressure. Standards and implementations, including RFC 8391, describe XMSS and XMSSMT parameter sets and usage. Implementations exist in libraries such as liboqs and some cryptographic toolchains.