SPHINCS+ (SLH-DSA)

SPHINCS+ (pronounced “SPHINCS plus”), now officially named SLH-DSA (Stateless Hash-Based Digital Signature Algorithm), is a post-quantum digital signature scheme standardized by NIST as FIPS 205. Unlike Kyber, Dilithium, and FALCON, which rely on the hardness of lattice problems, SPHINCS+ relies only on the security of hash functions. This makes it the most conservative choice in the NIST suite: if lattice-based schemes are ever broken by a novel attack, SPHINCS+ would remain secure as long as the underlying hash function (SHA-256 or SHAKE-256) is not broken.

Why hash-based signatures are conservative

The security of SPHINCS+ reduces to three properties of the hash function: collision resistance, second-preimage resistance, and a property called “undetectability” of pseudorandom function outputs. These are among the most well-studied and trusted assumptions in all of cryptography. No quantum algorithm breaks these properties more than quadratically (Grover’s algorithm provides at most a square-root speedup for collision search), and this speedup is accounted for in the parameter choices.

By contrast, lattice-based schemes depend on the hardness of structured algebraic problems (Module-LWE, NTRU) that, while extensively studied, have a shorter track record than hash function security. If a breakthrough in lattice algorithms were discovered (classical or quantum), the lattice-based standards would need to be replaced, but SPHINCS+ would be unaffected.

How SPHINCS+ works

SPHINCS+ combines three layers of hash-based signature primitives:

1. WOTS+ (Winternitz One-Time Signature): A one-time signature scheme where the signer hashes the secret key components a number of times determined by the message bits. Each WOTS+ key pair can sign exactly one message securely.

2. XMSS-like Merkle trees: Multiple WOTS+ key pairs are organized into binary Merkle trees. The root of each tree serves as the public key that authenticates all the leaves (WOTS+ public keys) beneath it. This allows many one-time signatures under a single public key.

3. Hypertree structure: Multiple layers of Merkle trees are stacked. The top-level tree signs the roots of second-level trees, which sign roots of third-level trees, and so on. The bottom-level trees sign the actual messages. This multi-layer structure is what makes SPHINCS+ practical: a single hypertree with enough leaves to sign $2^{64}$ messages would be too tall for efficient authentication paths.

The “stateless” property is critical. Earlier hash-based schemes (like XMSS) are stateful: the signer must track which one-time keys have been used and never reuse them. If state is lost or duplicated (e.g., from a backup restore), security breaks. SPHINCS+ avoids this by using a pseudorandom function to deterministically select which leaf to use for each message, ensuring that the same leaf is overwhelmingly unlikely to be reused across different messages.

Parameter sets and sizes

Parameter set	Security level	Public key	Signature	Secret key
SLH-DSA-128s	NIST Level 1 (small)	32 bytes	7,856 bytes	64 bytes
SLH-DSA-128f	NIST Level 1 (fast)	32 bytes	17,088 bytes	64 bytes
SLH-DSA-256s	NIST Level 5 (small)	64 bytes	29,792 bytes	128 bytes
SLH-DSA-256f	NIST Level 5 (fast)	64 bytes	49,856 bytes	128 bytes

The “s” variants minimize signature size at the cost of slower signing and verification. The “f” variants are faster but produce larger signatures. Even the smallest SPHINCS+ signatures (7,856 bytes at Level 1) are significantly larger than Dilithium signatures (2,420 bytes) or FALCON signatures (666 bytes).

The key sizes, however, are remarkably small: 32 or 64 bytes for public keys, compared to over 1,000 bytes for Dilithium and FALCON. This can matter for applications where key storage is constrained but signature transmission is not.

The trade-off

SPHINCS+ occupies a specific niche: maximum confidence in security, at the cost of large signatures and slower performance. It is the recommended backup option if lattice-based schemes are ever compromised. Organizations with extremely high security requirements, or those who want defense-in-depth against algorithmic breakthroughs, may choose SPHINCS+ for their most critical signing operations (e.g., signing firmware updates or root certificates) while using Dilithium for higher-volume, lower-stakes operations.

Why it matters for learners

SPHINCS+ teaches an important lesson about cryptographic design: the strongest security guarantees often come with practical costs. Hash-based signatures are the “belt and suspenders” of post-quantum cryptography. For quantum computing students, it also reinforces the point that Grover’s algorithm provides only a quadratic speedup (not exponential), which is manageable by doubling hash output lengths. This stands in stark contrast to Shor’s algorithm, which provides an exponential speedup against factoring and discrete logarithms.

See also

• NIST PQC Standards
• Post-Quantum Cryptography
• Dilithium (ML-DSA)
• FALCON (FN-DSA)