Hash-Based Signatures and SPHINCS+

Signatures Without Number Theory

Hash-based signature schemes are unique in cryptography because their security relies solely on the properties of cryptographic hash functions rather than the hardness of number-theoretic problems like integer factorization or discrete logarithms. Since no known quantum algorithm efficiently breaks hash functions (Grover's algorithm only provides a quadratic speedup, easily countered by doubling the hash output size), hash-based signatures are considered one of the most conservative and trustworthy approaches to post-quantum cryptography.

SPHINCS+ (selected by NIST as a post-quantum signature standard in 2022) is a stateless hash-based signature scheme. Unlike earlier hash-based schemes like XMSS that required signers to carefully track which one-time keys had been used (introducing dangerous state management requirements), SPHINCS+ uses a 'hypertree' of Merkle trees combined with a pseudorandom index selection mechanism. This means signers can generate signatures without maintaining any state between signing operations.

The tradeoff with hash-based signatures is size. A SPHINCS+-256s signature is approximately 29 KB, vastly larger than an Ed25519 signature (64 bytes) or even a Dilithium signature (2.4 KB). However, the minimal security assumptions (relying only on hash function pre-image and collision resistance) make SPHINCS+ an ideal 'insurance policy' signature scheme for scenarios demanding the highest possible confidence in long-term security, such as firmware signing for critical infrastructure.

Everyday Example

Imagine you need to sign 1,000 important documents. Most signature systems use a single, sophisticated fountain pen (elliptic curve math). It is elegant and compact, but a future technology might learn how to perfectly forge that pen. Hash-based signatures are like using 1,000 individual, completely disposable rubber stamps, each stamp used exactly once and then snapped in half. The stamps are bulky, but forging them requires physically recreating atomic-level rubber patterns, something no future technology can shortcut.

The Deep Mathematics

SPHINCS+ constructs a hypertree of height h = d × h', composed of d layers of XMSS trees each of height h'. Each leaf of the bottom-layer tree is the root of a FORS (Forest of Random Subsets) instance used for the actual message signing. FORS signs the message digest by revealing k randomly selected secret values from t sets of size 2^a, yielding a signature size proportional to k × (a + 1) × n, where n is the hash output length. Security reduces to the second pre-image resistance of the hash function: breaking the scheme requires finding x' ≠ x such that H(x') = H(x), which requires O(2ⁿ) evaluations classically or O(2^(n/2)) quantumly using Grover's algorithm.