# Hash-Based Signatures
Hash-based signatures are digital signature schemes whose security relies solely on the collision and preimage resistance properties of cryptographic hash functions, making them immune to quantum attacks beyond Grover's algorithm. Unlike RSA, ECDSA, or other classical signature schemes that depend on mathematical problems like integer factorization or discrete logarithms, hash-based signatures build their security foundation on hash functions that remain secure against quantum adversaries.
NIST standardized SPHINCS+ as SLH-DSA in August 2024, marking the first widely adopted hash-based signature standard for post-quantum cryptography. This standardization provides organizations with a conservative quantum-resistant alternative that assumes only the security of underlying hash functions like SHA-256 or SHAKE256. The approach offers the strongest theoretical security guarantees in the post-quantum cryptography portfolio because hash function security is better understood and more thoroughly analyzed than lattice-based or code-based mathematical assumptions.
Hash-based signatures exist to solve the quantum signature problem without introducing new cryptographic assumptions. While lattice-based signatures like Dilithium offer smaller signature sizes and faster performance, they depend on mathematical problems whose long-term security against quantum attacks remains uncertain. Hash-based signatures provide a fallback option that maintains security even if other post-quantum approaches prove vulnerable to future cryptanalytic advances.
The tradeoff for this conservative security approach is signature size. Hash-based signatures typically produce signatures 10-50 times larger than classical ECDSA signatures, making them suitable for applications where security confidence outweighs bandwidth efficiency. This positions them as the quantum-resistant equivalent of choosing AES-256 over AES-128: additional security margin in exchange for increased overhead.
Hash-based signatures build from one-time signature schemes that can sign exactly one message per key pair. The Lamport signature scheme, developed in 1979, demonstrates the core principle. The signer generates 512 random values as the private key and publishes their hashes as the public key. To sign a 256-bit message, the signer reveals 256 of the 512 private key values based on whether each message bit is 0 or 1. Anyone can verify the signature by hashing the revealed values and confirming they match the corresponding public key hashes.
Modern hash-based signatures use the Winternitz One-Time Signature (WOTS) scheme, which improves efficiency by signing multiple bits at once. Instead of signing individual bits, WOTS divides the message into chunks and uses hash chain iterations to represent larger values. For example, with parameter w=16, each chunk represents a 4-bit value from 0 to 15. The private key consists of random starting points for hash chains, and the public key contains the endpoints after multiple hash iterations. Signing reveals intermediate hash chain values, and verification checks that additional hashing reaches the public key endpoints.
The fundamental limitation of one-time signatures is their name: they work once. Using the same key pair to sign multiple messages reveals enough private key material to allow forgeries. Hash-based signature schemes solve this by organizing many one-time key pairs into Merkle tree structures.
A Merkle tree places WOTS public keys at the leaf nodes and builds a binary tree where each internal node contains the hash of its two children. The tree root serves as the overall public key for the hash-based signature scheme. To sign a message, the signer selects an unused WOTS key pair from the leaves, signs the message, and provides an authentication path consisting of sibling hashes from the selected leaf to the root. Verifiers can reconstruct the path to confirm the WOTS public key belongs to the tree and then verify the WOTS signature itself.
This Merkle tree approach enables multiple signatures from a single public key, with the number limited by tree height. A tree with height h supports 2^h signatures. Early schemes like XMSS required maintaining state to track which leaf keys had been used, creating operational challenges and security risks if state was lost or accidentally reused.
SPHINCS+ eliminates state management through a hypertree construction combined with randomization. Instead of a single large Merkle tree, SPHINCS+ uses multiple layers of smaller trees. The bottom layer contains Few-Time Signature Scheme (FORS) instances rather than one-time signatures. FORS can safely sign a small number of messages, providing efficiency improvements over pure one-time schemes.
The SPHINCS+ signing process works as follows. First, the message is hashed along with randomness to produce a digest and select a FORS instance within the hypertree structure. The selected FORS instance signs the message digest. Then, WOTS signatures authenticate the FORS public key up through the hypertree levels to the root public key. Each signature includes the FORS signature, the authentication path, and all intermediate WOTS signatures needed for verification.
The randomization in SPHINCS+ serves a critical security function. By including fresh randomness in each signature, SPHINCS+ ensures that even if the same message is signed multiple times, different parts of the hypertree are used. This prevents the statistical attacks that could otherwise compromise a stateless scheme through repeated signatures.
SPHINCS+ offers multiple parameter sets balancing security level, signature size, and signing speed. The "fast" variants prioritize performance with larger signatures, while "small" variants minimize signature size at the cost of slower signing. Security levels correspond to AES-128, AES-192, and AES-256 equivalent strength. Organizations can select parameters based on their specific security requirements and operational constraints.
The verification process reverses the signing steps. The verifier recomputes the message digest, follows the authentication paths through the hypertree to reconstruct the root public key, and confirms it matches the known public key. Unlike classical signatures that require modular exponentiation or elliptic curve operations, hash-based signature verification consists entirely of hash function evaluations, making it efficient and quantum-resistant.
Hash-based signatures represent the most conservative approach to quantum-resistant digital signatures because their security depends only on hash function properties that are well-understood and thoroughly analyzed. While other post-quantum signature schemes rely on mathematical assumptions about lattice problems, error-correcting codes, or multivariate equations, hash-based signatures require only that cryptographic hash functions resist collision and preimage attacks. This makes them the digital equivalent of keeping gold reserves while experimenting with new currencies.
The business impact of signature failure extends far beyond theoretical cryptography. Digital signatures authenticate software updates, validate financial transactions, and secure communications for critical infrastructure. A compromised signature scheme could enable attackers to forge software updates that bypass security controls, impersonate trusted parties in financial systems, or manipulate communications in industrial control networks. The cost of signature failure in a quantum world could reach trillions of dollars and threaten national security infrastructure.
Hash-based signatures provide insurance against this catastrophic risk. If lattice-based assumptions prove weaker than expected, or if mathematical breakthroughs compromise other post-quantum approaches, hash-based signatures remain secure as long as hash functions resist cryptanalysis. This fallback capability justifies their inclusion in quantum migration strategies despite larger signature sizes.
The signature size tradeoff varies significantly by application. Firmware signatures, certificate authority roots, and high-value financial transactions can accommodate kilobyte-sized signatures in exchange for decades of security confidence. Conversely, applications requiring thousands of signatures per second or operating under strict bandwidth constraints may find hash-based signatures impractical for general use while still valuable for bootstrapping trust in hybrid architectures.
Common misconceptions about hash-based signatures include the belief that their security is absolute or that signature size makes them unusable. Hash-based security depends on hash function security, which could theoretically be compromised by cryptanalytic advances or implementation flaws. However, hash functions are among the most studied and well-understood primitives in cryptography. Signature sizes, while large, continue decreasing through algorithmic improvements and parameter optimization. More importantly, many applications that require long-term security assurance can absorb the size overhead in exchange for cryptographic conservatism.
The failure to deploy hash-based signatures in appropriate use cases represents a strategic oversight in quantum preparedness. Organizations that rely exclusively on lattice-based alternatives assume mathematical risks they may not fully understand. Hash-based signatures provide a hedge against those risks and enable defense-in-depth approaches to post-quantum cryptography.
CDA positions hash-based signatures within the Data Protection and Sovereignty (DPS) domain as a foundational component of quantum migration strategies. The Sovereign Data Protocol demands that your data lives where you decide, period. This sovereignty extends to cryptographic dependencies: relying on a single post-quantum approach creates systemic risk that could compromise data sovereignty if that approach fails under quantum attack.
Our methodology differs from conventional post-quantum strategies that prioritize efficiency over security assurance. While industry consensus gravitates toward lattice-based signatures for general use, CDA advocates for hybrid approaches that incorporate hash-based signatures in high-assurance contexts. This reflects our defense-in-depth philosophy applied to cryptographic algorithm selection rather than just network architecture.
CDA recommends hash-based signatures for three specific use cases within DPS missions. First, firmware and software signing for critical infrastructure where signature verification happens infrequently but security requirements span decades. Second, certificate authority root keys and intermediate certificates where signature size has minimal operational impact but compromise consequences are severe. Third, authentication tokens and digital seals for sensitive documents where long-term integrity matters more than processing efficiency.
The integration approach combines hash-based signatures with lattice-based alternatives rather than replacing them entirely. Primary signing operations use efficient lattice-based schemes, while hash-based signatures secure the trust anchors and high-value operations that underpin the broader cryptographic architecture. This provides quantum resistance with practical performance while maintaining conservative security guarantees for the most critical components.
CDA's implementation guidance emphasizes operational security alongside algorithm selection. Hash-based signatures eliminate some implementation risks through their simplicity but require careful parameter selection and secure random number generation. Our deployment frameworks include guidance for selecting appropriate SPHINCS+ parameter sets, integrating hash-based signatures into existing public key infrastructures, and managing the operational overhead of larger signatures.
This approach recognizes that data sovereignty in the quantum era requires cryptographic sovereignty: the ability to maintain security even if primary cryptographic assumptions prove insufficient. Hash-based signatures provide that capability while remaining compatible with existing digital signature workflows and legal frameworks.
• Hash-based signatures depend only on hash function security, providing the most conservative quantum-resistant signature option independent of mathematical assumptions about lattice or other hard problems.
• NIST's standardization of SPHINCS+ as SLH-DSA in 2024 provides a stable foundation for deployment in high-assurance applications requiring long-term security confidence.
• Signature sizes are 10-50 times larger than classical schemes, making hash-based signatures suitable for firmware signing, certificate roots, and other applications where security outweighs bandwidth efficiency.
• The stateless design of modern hash-based signatures eliminates operational risks associated with key reuse while maintaining the fundamental security advantages of hash-only assumptions.
• Strategic deployment combines hash-based signatures with lattice-based alternatives in hybrid architectures that provide quantum resistance with practical performance and conservative fallback options.
• Post-Quantum Cryptography Migration Strategy • Certificate Authority Security and Quantum Resilience • Firmware Security and Supply Chain Integrity • Digital Signature Legal Frameworks and Compliance • Cryptographic Algorithm Lifecycle Management
• National Institute of Standards and Technology. "FIPS 203, 204, 205: Post-Quantum Cryptography Standards." August 2024.
• Bernstein, Daniel J., et al. "SPHINCS+: Submission to the NIST post-quantum project." NIST Post-Quantum Cryptography Standardization, 2019.
• Buchmann, Johannes, et al. "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions." RFC 8391, Internet Engineering Task Force, 2018.
• Chen, Lily, et al. "Report on Post-Quantum Cryptography." NIST Internal Report 8105, National Institute of Standards and Technology, 2016.