Reinventing a Classic: Hash-Based Signatures for a Quantum Era

In our first blog, we examined the looming risk posed by quantum computers to existing asymmetric key cryptographic standards, such as RSA (Rivest, Shamir, Adleman) and ECC (Elliptic Curve Cryptography). In the second, we explored how post-quantum cryptography (PQC) has emerged as a practical response, with the National Institute of Standards and Technology (NIST) standardizing algorithms like Federal Information Processing Standards (FIPS) 203 (Kyber) for key exchange and FIPS 204 (Dilithium) for digital signatures. Our third blog in this series continues this journey by now focusing on a different family of solutions: hash-based signatures. Unlike lattice-based schemes, these are not new inventions. They date back to the very origin of modern cryptography in the 1970s and, after decades of refinement, now feature prominently in NIST’s PQC standards. Before we delve deeper, let’s understand what’s really at stake. Digital signatures are the backbone of trust online; they confirm who sent a message (authenticity) and ensure it hasn’t been tampered with (integrity). From banking transactions to the software updates on smartphones, they keep the digital world running smoothly. The catch? These systems depend on problems that are currently difficult for classical computers to solve—but quantum computers could crack them in the near future, turning ‘secure’ into ‘vulnerable’ within hours.

The Foundation: Hash Functions and Their Security

A hash function is a mathematical mapping that takes any input and compresses it into a fixed-length output known as a hash or digest:

H:{0,1}^*→{0,1}ⁿ

No matter how long or short the input, the output length (e.g., 256 bits for SHA-256) is constant. This output acts like a digital fingerprint — unique to every input and impossible to reverse.

Figure 1: Hash Function, Tutorialspoint: https://www.tutorialspoint.com/cryptography/cryptography_hash_functions.htm

Even the smallest change in the input yields a completely different output. A Simple Example Let’s take a simple text example using SHA-256:       Now, change just one letter: “Hello world” (with a lowercase “w”)       Even though the difference is just a single character, the hash output changes completely. This is known as the avalanche effect, a defining property of high-quality hash functions. Behind the Scenes: How Hash Functions Work Hash functions are built using a compression-based iterative design. They divide the input data into small, fixed-length blocks (such as 512 bits) and process each block through several rounds of mathematical operations. Each round scrambles the data further, producing an output that appears random but is in fact deterministic—the same input always yields the same output. The final block is combined into a single fixed-length digest. This process ensures three important cryptographic properties:

• Diffusion: Every input bit influences many output bits.
• Determinism: The same input always yields the same hash.
• Irreversibility: The output reveals nothing about the input.

This architecture, simple yet mathematically sound, explains why hashes are used across nearly every cybersecurity system today. Password Protection: How Systems Keep You Safe When you create a password, the system does not store it directly. Instead, it’s passed through a hash function first, converting it into a unique digest before saving it to a database.       Later, when you log in, your password is hashed again, and the system compares the two hashes. If they match, you’re authenticated and access is granted, without your password ever being stored or revealed. To make this even stronger, modern systems add a salt (a random piece of data appended to your password before hashing). This ensures that even if two users choose identical passwords, they produce different hashes. NIST SP 800-63B: Digital Identity Guidelines and OWASP Password Storage Cheat Sheet emphasize salting and hashing (e.g., with SHA-256, bcrypt, or Argon2) as the foundation of secure password management.

Figure 2: Password Salting, Crbrary cyberhoot, May 06, 2020:

https://cyberhoot.com/cybrary/password-salting/

The Three Pillars of Hash-based Security

To be considered secure, a hash function H must satisfy three essential properties:

1. Preimage Resistance: It should be computationally infeasible to determine the original input x (preimage) from its hash output H(x). This ensures that even if someone sees the hash, they cannot reverse-engineer the input.

1. Second-Preimage Resistance: Given one input x₁ and its hash H(x₁), it should be infeasible to find another x₂ with the same hash.
2. Collision Resistance: It should be infeasible to find any two inputs that yield the same hash output.

These properties make hash functions a foundational tool in cryptography, digital signatures, password storage, and data integrity verification.

Figure 3: Three security pillars of Hash function

 Where Hashes Are Used Today

Application	Example	Role of Hashing
Password Authentication	Login systems and cloud identity services	Stores salted hashes instead of passwords
Data Integrity	File checksums and software updates	Detects any unauthorized modification
Digital Signatures	Code signing and document signing	Hashes data before signature for efficiency
Blockchain Networks	Bitcoin and Ethereum	Links blocks and ensures immutability
APIs & Communication	TLS, OAuth, and HMAC	Verifies authenticity and message integrity
Certificates (PKI)	HTTPS and S/MIME	Validates certificate integrity and authenticity

Table 1: Application of Hash Function in our daily life

Looking beyond current applications, an important question arises: how resilient are hash functions against quantum computing?

Quantum Resilience

Hash functions are considered quantum-resistant. Quantum algorithms, such as Shor’s, threaten RSA and ECC, but hash functions employ non-algebraic logic, making them less vulnerable. Only Grover’s algorithm offers a partial quadratic speed-up through brute force. In effect, SHA-256 delivers about 128-bit post-quantum security, and SHA-512 provides even more. Hash-Based Signatures: From Theory to Practice Due to their resilience, hash functions have evolved into comprehensive post-quantum digital signature systems—collectively known as Hash-Based Signatures (HBS). Stateful vs. Stateless: The Two Families of HBS Stateful schemes (LMS, XMSS):

• Each signature consumes a unique portion of key material that must not be reused.
• The signer keeps track of which keys have been used — this record is called the state.
• Ideal for environments where state tracking is possible (firmware signing, IoT devices).

Stateless schemes (SPHINCS+):

• Do not require tracking previous keys.
• Use a hierarchy of Merkle trees to derive new signing keys independently each time.
• Perfect for distributed or large-scale cloud systems.

Figure 4: Stateful and Stateless Hash Function, geeksforgeeks, September 19, 2025:

https://www.geeksforgeeks.org/system-design/stateful-vs-stateless-architecture/

LMS and XMSS: Practical (Stateful) Hash-Based Signatures

The Leighton–Micali Signature (LMS) and eXtended Merkle Signature Scheme (XMSS) are standardized by the Internet Engineering Task Force (IETF), the global standards body responsible for internet protocols and cryptographic specifications, and have been adopted by various enterprises for use cases such as  in firmware signing and IoT security, where their efficiency and conservative design are highly valued. Their core advantage: they rely purely on hash functions, avoiding the complex algebraic vulnerabilities that quantum computers exploit. Their main drawback is the need for accurate tracking: each signature uses a portion of the private key, so signers must ensure no part is used twice. Reusing key parts may compromise security and leak sensitive information. In controlled settings, this tracking is manageable; however, it creates operational risk when deployed at an enterprise scale.

The Stateless Breakthrough: SPHINCS+

To overcome the operational risks of stateful systems like LMS and XMSS, researchers introduced SPHINCS in 2015, the first practical stateless hash-based signature scheme. The advantage is clear: there was no danger of accidentally reusing private key components. But the trade-off was efficiency. SPHINCS produced much larger signatures, often tens of KBs, and operations were slower than those of lattice-based schemes. This design was later refined into SPHINCS+, which reduced signature sizes, improved performance, and strengthened its security guarantees. +, standardized as the Stateless Hash-Based Digital Signature Algorithm (SLH-DSA: FIPS 205), as part of its first set of PQC standards, ensuring that hash-based cryptography remains a cornerstone in the post-quantum world.¹

Conclusion

The story of hash-based signatures highlights a central truth of post-quantum cryptography: resilience comes from diversity. While lattice-based cryptography may lead in speed and scalability, hash-based schemes offer robust security built on decades of rigorous analysis. NIST’s inclusion of SPHINCS+ alongside lattice-based algorithms reflects this balance. For enterprises, it is a reminder that preparing for the quantum era is not about choosing a single “winner” but about building a portfolio of cryptographic tools. In that portfolio, hash-based signatures serve as the conservative anchor, ensuring that the transition to quantum-safe security rests on the most dependable foundations available. In our upcoming blog, we will explore how enterprises can begin adopting PQC: from identifying current cryptographic dependencies to implementing hybrid, quantum-safe strategies across their digital . Ready to future-proof your security? Explore Quantum-Safe Cryptography now and learn how to build a resilient, hybrid strategy for the post-quantum era.

References:

¹ NIST Releases First 3 Finalized Post-Quantum Encryption Standards, Chad Boutin, nist.gov, August 13, 2024: https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards ² Stateless Hash-Based Digital Signature Standard, National Institute of Standards and Technology, csrc.mist.gov, August 13, 2024: https://csrc.nist.gov/pubs/fips/205/final ³ Digital Identity Guidelines Authentication and Lifecycle Management, Paul A. Grassi, James L. Fenton, Elaine M. Newton, Ray A. Perlner, Andrew R. Regenscheid, William E. Burr, Justin P. Richer, Naomi B. Lefkovitz, Jamie M. Danker, Yee-Yin Choong, Kristen K. Greene, Mary F. Theofanos, nvlpubs.nist.gov, Feb 03, 2020: https://nvlpubs.nist.gov/nistpubs/specialpublications/nist.sp.800-63b.pdf ⁴ Password Storage Cheat Sheet, OWASP: https://cheatsheetseries.owasp.org/cheatsheets/Password_Storage_Cheat_Sheet.html ⁵ SHA-256, csrc.nist.gov: https://csrc.nist.gov/glossary/term/sha_256 ⁶ Leighton-Micali Hash-Based Signatures, D. McGrew, M. Curcio, S. Fluhrer, datatracker.ietf.org, April 2019: https://datatracker.ietf.org/doc/html/rfc8554 ⁷ eXtended Merkle Signature Scheme, A. Huelsing, D. Butin, S. Gazdag, J. Rijneveld, A. Mohaisen, datatracker,  May 2018: https://datatracker.ietf.org/doc/html/rfc8391