Introduction
Modern public-key cryptography protects everything from software updates and digital documents to secure communications and authentication systems. However, advances in quantum computing could eventually threaten several widely used public-key algorithms.
Algorithms based on integer factorization and discrete logarithms, including RSA and elliptic-curve-based signatures, are considered vulnerable to sufficiently powerful quantum computers. This has accelerated the development of post-quantum cryptography (PQC).
One important approach is hash-based signatures. Instead of relying on the mathematical problems behind RSA or elliptic-curve cryptography, hash-based signature schemes rely primarily on the security properties of cryptographic hash functions.
This makes them an important part of the post-quantum security landscape.
In 2024, NIST finalized FIPS 205, the Stateless Hash-Based Digital Signature Standard (SLH-DSA), based on SPHINCS+. It is now one of the standardized post-quantum digital signature options organizations can implement.
This guide explains hash-based signatures, how they work, how they differ from traditional signatures, and why they matter for post-quantum cryptography.
What Are Hash-Based Signatures?
Hash-based signatures are digital signature schemes that use cryptographic hash functions as their fundamental security building blocks.
Traditional public-key signatures often depend on mathematical assumptions such as the difficulty of factoring large integers or solving discrete logarithm problems.
Hash-based signatures take a different approach.
They construct digital signatures using one-way cryptographic hash functions and structures such as Merkle trees.
The basic idea is:
Private key → hash-based signing components → Merkle tree → public key
A signature proves that the signer possesses the required secret information without exposing that secret information to the recipient.
Because their security is based primarily on well-studied hash-function properties rather than factoring or discrete logarithms, hash-based signatures are considered an important candidate for quantum-resistant digital signatures.
Why Do We Need Post-Quantum Digital Signatures?
Quantum computers are fundamentally different from classical computers.
A sufficiently capable quantum computer could use algorithms such as Shor’s algorithm to attack the mathematical problems underlying widely used public-key cryptography.
This creates a long-term security concern for systems that depend on RSA, ECDSA, and related algorithms.
The concern extends beyond encrypted communications.
Digital signatures are used to establish trust in:
- Software updates
- Firmware
- Digital documents
- Certificates
- Secure communications
- Code-signing systems
- Device authentication
- Supply-chain security
If an attacker could forge a trusted signature, they could potentially make malicious software or altered data appear authentic.
This is why organizations are beginning the transition to post-quantum digital signatures before large-scale cryptographically relevant quantum computers become available.
NIST’s current PQC guidance encourages organizations to begin migration rather than wait for a practical quantum computer.
How Do Hash-Based Signatures Work?
The underlying concept becomes easier to understand by starting with a one-time signature.
A one-time signature is designed to sign a message securely using a particular secret signing state only once.
One-time signature constructions can then be combined into larger structures.
A Merkle tree provides a way to organize many one-time signing keys.
Each leaf represents a cryptographic value associated with a signing key. Hashes are repeatedly combined to create higher levels until a single root value is produced.
That root becomes part of the public key.
When a message is signed, the signer provides:
- The signature generated from the appropriate secret signing material.
- The information needed to demonstrate the corresponding public value.
- A Merkle authentication path connecting that value to the public root.
The verifier can then calculate the required hashes and confirm that the resulting root matches the public key.
This is the basic concept behind several hash-based signature constructions.
What Is a Merkle Tree?
A Merkle tree is a tree-shaped cryptographic data structure in which nodes are generated using hash functions.
A simplified structure looks like this:
Root Hash
/ \
Hash A Hash B
/ \ / \
Hash 1 Hash 2 Hash 3 Hash 4
/ \ / \ / \ / \
L1 L2 L3 L4 L5 L6 L7 L8
The leaves can represent values associated with one-time signatures.
The root summarizes the entire structure.
During verification, a Merkle authentication path allows the verifier to confirm that a particular leaf belongs to the tree without receiving the entire tree.
This approach is one of the fundamental ideas behind hash-based digital signatures.
Hash Functions and Their Security Properties
Hash functions convert an input of arbitrary length into a fixed-length output called a digest.
For example:
Message → Cryptographic Hash Function → Digest
Security-focused hash functions are expected to provide several important properties.
Preimage Resistance
Given a hash output, it should be computationally difficult to find an input that produces that output.
Second-Preimage Resistance
Given one input, it should be difficult to find a different input that produces the same hash.
Collision Resistance
It should be computationally difficult to find two different inputs that produce the same hash value.
These properties are important because hash-based signatures depend heavily on the security of their underlying hash functions.
From HORS to Modern Hash-Based Signatures
The original article discussed HORS (Hash to Obtain Random Subset) and used MD5 in its simplified example.
That example is no longer appropriate for a modern cryptography article.
MD5 is considered cryptographically broken for collision resistance and should not be presented as a secure choice for new digital-signature systems.
Modern hash-based signature systems use stronger cryptographic constructions and standardized algorithms.
The most important current example is SLH-DSA.
What Is SLH-DSA?
SLH-DSA, or Stateless Hash-Based Digital Signature Algorithm, is specified in NIST FIPS 205.
It is based on the SPHINCS+ submission from the NIST Post-Quantum Cryptography Standardization process.
Unlike stateful schemes, SLH-DSA does not require the signer to maintain and correctly update a signing state between signatures.
This is an important operational advantage because accidentally reusing signing state can create serious security problems in stateful signature systems.
NIST selected SLH-DSA as one of its standardized post-quantum digital signature algorithms.
SLH-DSA vs ML-DSA
Hash-based signatures are not the only standardized post-quantum signature technology.
NIST also standardized ML-DSA, a lattice-based digital signature algorithm, in FIPS 204.
| Feature | SLH-DSA | ML-DSA |
| Cryptographic approach | Hash-based | Lattice-based |
| NIST standard | FIPS 205 | FIPS 204 |
| Stateless | Yes | Yes |
| Based on | SPHINCS+ | CRYSTALS-Dilithium |
| Main strength | Different mathematical foundation | Performance and practical deployment |
| Main consideration | Larger signatures | More complex mathematical assumptions |
NIST describes SLH-DSA as an alternative signature approach based on a different mathematical foundation from ML-DSA. This diversity can be valuable when organizations design long-term post-quantum cryptographic strategies.
What Are XMSS and LMS?
Two other important hash-based signature families are XMSS and LMS.
XMSS stands for eXtended Merkle Signature Scheme. It is a stateful hash-based signature system standardized through RFC 8391.
LMS stands for Leighton-Micali Signature. It is also a stateful hash-based signature system and is specified in RFC 8554.
The key distinction is that stateful schemes require careful management of the signing state.
A signing key must not accidentally reuse the same one-time signing material.
This makes key-management procedures particularly important when deploying XMSS or LMS.
Stateful vs Stateless Hash-Based Signatures
| Characteristic | Stateful HBS | Stateless HBS |
| Examples | XMSS, LMS | SLH-DSA |
| Signing state | Must be maintained | No persistent signing state required |
| Key management | More demanding | Operationally simpler |
| Signature approach | Hash-based | Hash-based |
| Standardization | Established standards | NIST FIPS 205 |
| Suitable use | Controlled environments | Broader deployment scenarios |
The choice depends on the application, implementation constraints, performance requirements, and operational environment.
Advantages of Hash-Based Signatures
Hash-based signatures offer several important advantages.
Quantum Resistance
Their security does not depend on the factoring or discrete-logarithm problems targeted by Shor’s algorithm.
Well-Studied Building Blocks
They rely heavily on cryptographic hash functions, which have been extensively studied.
Algorithmic Diversity
SLH-DSA provides a standardized post-quantum signature option based on a different mathematical foundation from ML-DSA.
Strong Authentication
Digital signatures can verify the authenticity and integrity of signed information.
Useful for Long-Lived Systems
Hash-based signatures can be particularly interesting for systems where software, firmware, or documents may need trustworthy signatures for many years.
Limitations of Hash-Based Signatures
Hash-based signatures are not perfect for every application.
Depending on the scheme and security level, they can involve:
- Larger signatures
- Larger public keys than some traditional systems
- More computation or bandwidth than conventional signatures
- Stateful key-management challenges for XMSS and LMS
- Different implementation requirements
Therefore, organizations should select a standardized algorithm based on the application’s requirements rather than assuming that one post-quantum algorithm is ideal for every situation.
How Organizations Should Prepare for Post-Quantum Cryptography
Post-quantum migration is not simply a matter of replacing one algorithm.
Organizations should first understand where cryptography is being used.
A practical migration process includes:
Identify where RSA, ECDSA, Diffie-Hellman, and other public-key algorithms are used.
- Identify long-lived assets
Prioritize systems, software, certificates, firmware, and data that need protection for many years.
- Evaluate standardized PQC algorithms
Consider ML-KEM for key establishment and ML-DSA or SLH-DSA for digital signatures where appropriate.
- Test interoperability
PQC algorithms can introduce changes to key sizes, signatures, protocols, and infrastructure.
- Design crypto-agile systems
Applications should make it possible to replace cryptographic algorithms without rebuilding the entire system.
- Begin migration early
NIST’s transition work identifies a long-term move away from quantum-vulnerable public-key algorithms, with its current planning aimed at completing the transition by 2035.
Frequently Asked Questions
Are hash-based signatures quantum resistant?
Hash-based signatures are designed to resist attacks from quantum computers under appropriate security assumptions about their underlying hash functions. SLH-DSA is specifically standardized by NIST as a post-quantum digital signature algorithm.
Is SLH-DSA the same as SPHINCS+?
SLH-DSA is the standardized NIST algorithm derived from SPHINCS+. SPHINCS+ was the submission selected through the NIST standardization process, while SLH-DSA is the name used in the final FIPS 205 standard.
Are RSA and ECDSA quantum safe?
No. RSA and elliptic-curve-based public-key algorithms are considered vulnerable to sufficiently powerful quantum computers. Organizations are therefore preparing for migration to post-quantum alternatives.
What is the difference between XMSS and SLH-DSA?
XMSS is a stateful hash-based signature scheme. SLH-DSA is a stateless hash-based signature algorithm standardized in NIST FIPS 205. Stateful schemes require careful tracking of signing state, while SLH-DSA avoids that operational requirement.
Which hash-based signature algorithm should organizations use?
There is no universal answer. For new systems, organizations should evaluate standardized algorithms such as SLH-DSA against their security, performance, interoperability, and operational requirements. Existing systems using XMSS or LMS may have specific reasons to retain those schemes.
Conclusion
Hash-based signatures have become an important part of the post-quantum cryptography landscape.
The technology offers an alternative to public-key signatures based on mathematical problems that could eventually be attacked by sufficiently powerful quantum computers. Instead, hash-based approaches rely primarily on the security properties of cryptographic hash functions.
The landscape has also moved well beyond the early HORS and MD5 examples often used in older explanations. SLH-DSA is a finalized NIST post-quantum standard under FIPS 205, while XMSS and LMS remain important stateful hash-based signature technologies.
For organizations, the larger lesson is clear: post-quantum security is now a migration project rather than a purely theoretical research topic.
Build a cryptographic inventory. Identify vulnerable systems. Test standardized post-quantum algorithms. Improve crypto agility. And plan the transition before quantum computing creates an urgent security deadline.