SPHINCS+ Hash-Based Signatures: Stateless Design, Security Tradeoffs, and Post-Quantum Relevance

SPHINCS+ hash-based signatures represent one of the most conservative and well-understood approaches to post-quantum cryptography standardised by NIST. Unlike lattice or code-based schemes, SPHINCS+ grounds its security in the collision resistance of hash functions, a property cryptographers have trusted for decades. This article explains exactly how SPHINCS+ works, why its stateless architecture matters, how it compares to lattice-based alternatives, and what the real-world tradeoffs look like for developers and security architects choosing a post-quantum signature scheme today.

What Are Hash-Based Signatures?

Hash-based signature schemes (HBS) derive their security entirely from the properties of cryptographic hash functions, specifically preimage resistance, second-preimage resistance, and collision resistance. There is no algebraic structure to attack, no lattice problem to solve, and no integer factorisation to reverse. If the underlying hash function holds, the signature scheme holds.

This conservatism is the defining feature. Hash functions like SHA-256 and SHAKE-256 have survived decades of intense cryptanalysis. Their security assumptions are narrower and better understood than those underlying elliptic-curve cryptography (ECDSA), RSA, or even the newer lattice-based schemes.

From Lamport to SPHINCS+: A Brief Lineage

The lineage runs through several generations:

• Lamport OTS (1979): The original one-time signature. Each key pair can sign exactly one message. Secure but wildly impractical for general use.
• Winternitz OTS+ (W-OTS+): Compresses key and signature sizes by signing multiple bits per hash chain, reducing output at the cost of more computation per verification.
• XMSS (eXtended Merkle Signature Scheme): A stateful scheme. Uses a Merkle tree of one-time keys, tracking which leaf has been consumed. Secure and efficient, but statefulness is operationally dangerous. Reusing a leaf index breaks security completely.
• SPHINCS (2015) and SPHINCS+ (2019): Eliminated the statefulness problem. SPHINCS+ builds a hyper-tree structure of Merkle trees to achieve stateless signing without any index management.

SPHINCS+ was submitted to the NIST Post-Quantum Cryptography (PQC) standardisation process in round 1 and selected as a standard in 2022. It is now formally published as SLH-DSA under FIPS 205 (draft finalised 2024).

---

How SPHINCS+ Achieves Stateless Signing

The core engineering problem with earlier hash-based schemes is state. When you sign with XMSS, you must never reuse a one-time key. In practice, this requires persistent, synchronised state across all signing instances, a nightmare for distributed systems, hardware security modules with failover, or any environment where the signer might restart, crash, or be replicated.

SPHINCS+ solves this with a hyper-tree, a multi-layer construction of Merkle trees where the leaf selection for each signing operation is derived pseudorandomly from the message and a secret random value, rather than from a counter.

The Hyper-Tree Structure

At a high level, SPHINCS+ works as follows:

1. Top-layer Merkle tree: The public key is the root of this tree.
2. Intermediate layers (d layers total): Each internal node is itself the root of a smaller Merkle tree called an XMSS tree. Signatures on intermediate nodes authenticate the layer below.
3. Bottom layer — FORS (Forest of Random Subsets): The actual message is signed using FORS, a few-time signature scheme that selects subsets of leaves pseudorandomly based on a hash of the message.

Because leaf selection is determined by a pseudorandom function (PRF) keyed on the secret key and a random value drawn fresh per signature, no external state counter is needed. The signer does not track which leaves have been used. The randomness makes reuse astronomically unlikely.

Parameter Sets and Their Effect on Size

SPHINCS+ offers a range of parameter sets that trade signature size for security level and speed. The three core families are:

The "s" (small) variants use deeper hyper-trees, producing smaller signatures but requiring more hash computations per signing operation. The "f" (fast) variants use wider, shallower trees, producing larger signatures but signing much faster.

For comparison, an ECDSA signature over P-256 is 64 bytes. A SPHINCS+ signature at equivalent post-quantum security is 7,900 to 49,000 bytes. This size difference is the central tradeoff of the scheme.

---

Security Assumptions: What SPHINCS+ Actually Relies On

SPHINCS+ security reduces to two properties:

1. Pseudorandom Function (PRF) security: The key derivation and randomness generation must behave as a PRF. This is a standard, well-studied assumption.
2. Hash function collision and preimage resistance: The Merkle tree constructions require that SHA-256 or SHAKE-256 (depending on the parameter set chosen) cannot be broken in the relevant sense.

There is no assumption about the hardness of any algebraic problem. No hidden mathematical structure. If SHA-256 and SHAKE-256 remain secure, SPHINCS+ remains secure, including against quantum computers running Grover's algorithm. Grover's algorithm provides a quadratic speedup for unstructured search, which effectively halves the bit-security of a hash function. This is why SPHINCS+ at the 128-bit post-quantum security level uses hash outputs of 256 bits, preserving 128 bits of security after Grover.

This is a fundamentally different risk profile from lattice schemes like ML-DSA (Dilithium) or ML-KEM (Kyber), whose security relies on the hardness of problems such as Module-LWE (Learning With Errors). Those problems are believed to be quantum-hard, but they are newer to rigorous cryptanalysis, and the history of lattice cryptanalysis has produced meaningful parameter adjustments over time.

No Structural Attacks

A structural break of SPHINCS+ would require either:

• Breaking the underlying hash function, or
• A flaw in the hyper-tree construction itself (which has been extensively peer-reviewed through the NIST process)

This makes SPHINCS+ the most conservative choice among NIST's selected post-quantum signature standards, suitable for applications where a conservative security posture is worth the bandwidth and storage cost.

---

SPHINCS+ vs Lattice-Based Signatures: A Clear Comparison

NIST standardised three post-quantum signature algorithms. Understanding the tradeoffs is essential for architects:

Key insight: Falcon achieves the smallest signatures but its signing algorithm requires careful handling of floating-point arithmetic, creating implementation pitfalls. ML-DSA (Dilithium) is the practical general-purpose choice. SPHINCS+ is the conservative fallback, ideal where signature sizes are tolerable and minimising cryptographic assumption risk is paramount.

---

Real-World Applications and Deployment Scenarios

Long-Lived Document Signing and Root CA Certificates

Certificate authorities (CAs) and timestamping authorities need signatures that remain verifiable for decades. The risk of "harvest now, decrypt later" attacks, where adversaries store signed documents today and verify them once quantum computers mature, makes conservative signature schemes attractive at the root level. SPHINCS+ is a natural fit here: signature sizes are large, but root certificates are not transmitted frequently, and the conservative security assumption justifies the overhead.

Firmware and Code Signing

Embedded systems, firmware images, and software packages are signed once and verified many times. The verification overhead of SPHINCS+ is acceptable. More importantly, an HSM or air-gapped signing system does not need to maintain state, eliminating a class of operational failures unique to stateful schemes.

Blockchain and Cryptocurrency Wallets

This is where signature size becomes a genuine cost. A blockchain that must include signatures in every transaction block will feel the bandwidth and storage impact of 8 to 50 KB signatures acutely. Bitcoin currently uses ~72-byte ECDSA signatures. Moving to SPHINCS+ at 128-bit post-quantum security would increase per-transaction data by roughly 100x.

Projects building post-quantum secure wallets must weigh this carefully. Some choose layered approaches: SPHINCS+ at the root (key generation, address derivation) and ML-DSA for transaction signing, accepting lattice-based assumptions for day-to-day operations while keeping the most sensitive operations under conservative hash-only assumptions. BMIC.ai, for example, is building lattice-based post-quantum cryptography into its wallet architecture, recognising that NIST's full suite of PQC standards, including hash-based options, provides layered defence against Q-day risks.

TLS and Network Protocols

SPHINCS+ is not well suited to TLS handshakes, where latency is critical and every kilobyte of handshake data matters. ML-DSA dominates here. IETF working groups are actively standardising hybrid PQC schemes for TLS 1.3 that combine classical ECDSA with ML-DSA, with SPHINCS+ reserved for certificate chain roots where the size penalty is absorbed once per session.

---

Implementation Considerations

Side-Channel Resistance

SPHINCS+ has a significant advantage: because its operations are hash computations rather than modular arithmetic or polynomial multiplication, it is comparatively straightforward to implement in constant time. Hash functions have well-understood, hardware-accelerated constant-time implementations on most modern platforms. This contrasts with Falcon, where the Gaussian sampling step requires careful mitigation of timing side channels.

Available Libraries

Mature, audited implementations exist in:

• PQClean: Reference C implementations of all NIST PQC finalists, including all SPHINCS+ parameter sets.
• liboqs (Open Quantum Safe): Drop-in library supporting SPHINCS+ alongside Kyber, Dilithium, and Falcon. Integrates with OpenSSL and BoringSSL via the OQS-Provider.
• Bouncy Castle (Java/C#): Supports SPHINCS+ as part of its PQC module.
• Rust: pqcrypto crate: Wraps PQClean implementations for use in Rust projects.

Hybrid Deployment

Current best practice from NIST, IETF, and BSI (Germany's federal security agency) is hybrid signature schemes during the migration period: sign with both a classical algorithm and a post-quantum algorithm. Verifiers that understand PQC validate both; legacy verifiers fall back to the classical signature. This provides a security floor regardless of which assumption breaks first.

---

Why Hash-Based Signatures Still Matter

The NIST PQC process was explicitly designed to avoid relying on a single algebraic family. Lattice cryptography has made rapid progress, but it is a younger field than hash function cryptanalysis. History shows that algebraic problems sometimes fall in unexpected ways. AES and SHA-3 survived their competitions because they were subjected to intense scrutiny from the global cryptographic community. SPHINCS+ offers a hedge: if lattice assumptions are ever weakened by classical cryptanalysis, the hash-only fallback remains intact.

For security architects operating under long time horizons, regulatory mandates, or compliance frameworks that demand conservative assumptions, SPHINCS+ and its FIPS 205 standardisation as SLH-DSA provides exactly that hedge. The signature sizes are a cost worth paying when the alternative is catastrophic key compromise.