Short answer: SPHINCS+ is a stateless hash-based signature framework whose security relies on the properties of hash functions. Its designers describe it as authenticating a huge number of few-time signature key pairs using a hypertree, with a new few-time scheme called FORS. The sources here are the designers' own specification and paper from the time of NIST's second round. NIST later published SLH-DSA in FIPS 205, which is based on SPHINCS+.

Where hash-based signatures come from

The SPHINCS+ specification traces hash-based signatures to Lamport in the late 1970s, extended to more signatures by Merkle. It says the security of these schemes is easy to analyze and relies solely on the properties of the hash function. Merkle's tree-based scheme, however, required fixing at key generation the number of signatures to be made, and required the user to remember a state: how many signatures had already been made with the key.

The stateful and stateless split

The specification says that in the 40 years since Lamport's scheme many ideas improved performance and practicality, culminating in XMSS, which it describes as being in the last phase of standardization by the CFRG at that time. Its strong point is that it needs very few security assumptions, and the hash function even need not be collision resistant. Its downside, the specification says, is that it is stateful, which makes it fit poorly with the standard definition of a signature scheme as stated in NIST's call for submissions.

SPHINCS was designed by Bernstein, Hopwood, Hulsing, Lange, Niederhagen, Papachristodoulou, Schneider, Schwabe and Wilcox-O'Hearn as a stateless hash-based signature scheme, and the specification says it was the first signature scheme to propose parameters to resist quantum cryptanalysis. It uses many components from XMSS but works with larger keys and signatures to eliminate the state.

The hypertree

The specification says the basic idea of SPHINCS+, as in SPHINCS, is to authenticate a huge number of few-time signature (FTS) key pairs using a hypertree. The 2019 paper describes a hypertree as a tree of trees, linked together using one-time signatures. As leaf nodes are randomly selected, there is a trade-off between the size of the tree and the likelihood of selecting the same leaf twice. Using an FTS at the bottom of the tree shifts the trade-off toward smaller trees.

What SPHINCS+ changed

The paper's abstract says SPHINCS+ has significant advantages over the state of the art in speed, signature size and security, and was among the nine remaining signature schemes in NIST's second round. Those are the authors' claims at that time. Its main contributions are a new few-time signature scheme called FORS and tweakable hash functions, which it says allow a unified security analysis of hash-based signature schemes. The paper also says SPHINCS+ replaced SPHINCS's leaf selection with publicly verifiable index selection. It gives a security reduction, derives parameters from the resulting bound and presents speed results compared with SPHINCS-256, Gravity-SPHINCS and Picnic.

What this does not tell you

These documents do not give final parameter sets, signature sizes or timings for the standardized SLH-DSA, and they predate it. For the standard itself, read FIPS 205.

FAQ

What is SPHINCS+?

A stateless hash-based signature framework, from the paper's abstract.

Why stateless?

Merkle-style schemes make the user remember how many signatures were made. SPHINCS removes that state at the cost of larger keys and signatures, per the specification.

What is FORS?

A new few-time signature scheme introduced in SPHINCS+, per the paper.

What is a hypertree?

A tree of trees linked with one-time signatures, per the 2019 paper.

How does it relate to SLH-DSA?

SLH-DSA, standardized in FIPS 205, is based on SPHINCS+. These documents come from before standardization.

All field notes