Hash-Based Signatures

The most conservative approach to quantum-resistant digital signatures.

Technical Explanation

Hash-based signatures evolved from Lamport's one-time signatures (1979) — a beautifully simple construction where signing reveals preimages of hash values. The challenge has been extending one-time schemes to support multiple signatures.

Evolution of Hash-Based Signatures

Why Hash-Based Security is Conservative

Hash-based signatures rely on minimal assumptions:

• Collision resistance — Finding H(x) = H(y) for x ≠ y is hard
• Second-preimage resistance — Given x, finding y where H(x) = H(y) is hard
• Preimage resistance — Given H(x), finding x is hard

Quantum Resistance

Against quantum computers:

• Shor's algorithm — Does NOT apply (no group structure to exploit)
• Grover's algorithm — Provides only √n speedup on preimage search
• Mitigation — Double the hash output size defeats Grover's speedup

SPHINCS+ (SLH-DSA) — The NIST Standard

SPHINCS+ (standardized as SLH-DSA/FIPS 205) solves the statefulness problem using a clever hypertree construction:

SPHINCS+ Architecture:
├── Hypertree (d layers of XMSS trees)
│   └── Each tree authenticates the next layer
├── WOTS+ One-Time Signatures
│   └── Signs inter-layer roots
└── FORS Few-Time Signatures
    └── Signs actual message

SPHINCS+ Parameter Options

SynX Relevance

Hash-Based vs. Lattice-Based Signatures

Related Terms

• SLH-DSA — NIST's official name for SPHINCS+
• SPHINCS+ — The underlying algorithm
• Hash-Based Cryptography — The broader category
• WOTS+ — Winternitz One-Time Signature Plus
• Merkle Tree — The key data structure
• FIPS 205 — The NIST standard document