Hash-Based Signatures
Expert-defined terms from the Professional Certificate in Post-Quantum Cryptography course at London School of Business and Administration. Free to read, free to share, paired with a professional course.
A – The first letter of the alphabet, often used as a prefix in naming sc… #
In hash‑based signatures, “A” may appear in abbreviations like A‑OS (Authenticated One‑Shot) to denote a specific construction variant.
Adaptive Security – A security notion that requires a scheme to remain se… #
In the context of hash‑based signatures, adaptive security ensures that the compromise of one‑time keys does not endanger future signatures. Related terms: Chosen‑Message Attack, Forward Security. Example: The XMSS scheme provides adaptive security by limiting the number of signatures per leaf node.
Aggregate Signatures – A technique that combines multiple signatures on d… #
While traditional aggregate signatures rely on algebraic structures like bilinear pairings, hash‑based aggregate signatures are an emerging research area. They aim to retain the post‑quantum resistance of hash‑based primitives while reducing bandwidth. Related terms: Multi‑Signature, Batch Verification. Challenge: Designing an aggregation method that does not compromise the one‑time nature of underlying OTS components.
Authenticated Encryption – A cryptographic primitive that simultaneously… #
Though not a signature scheme, authenticated encryption is often paired with hash‑based signatures in protocols to protect message payloads. Related terms: AEAD, GCM. Example: A client may encrypt a payload with AES‑GCM and then sign the ciphertext using an XMSS private key.
Binary Merkle Tree – A tree data structure where each non‑leaf node is th… #
Binary Merkle trees are the backbone of many hash‑based signature schemes, providing efficient authentication paths for one‑time public keys. Related terms: Merkle Root, Authentication Path. Practical application: In the LMS (Leighton‑Micali Signature) scheme, the Merkle tree enables a signer to prove ownership of a specific OTS key without revealing the entire tree.
Certificate Transparency – An open framework for monitoring and auditing… #
When hash‑based signatures are used for code signing, Certificate Transparency logs can record the hash of the signed artifact, enabling third parties to detect misissued certificates. Related terms: CT Log, Signed Certificate Timestamp. Challenge: Integrating post‑quantum signatures into existing CT infrastructure while preserving compatibility with legacy browsers.
Chain of Trust – A hierarchical model where each entity’s public key is c… #
In a post‑quantum environment, hash‑based signatures can replace RSA or ECDSA signatures at any level of the chain. Related terms: Root Certificate, Intermediate CA. Example: A firmware update may be signed with a SPHINCS+ key, and the public key is certified by a traditional CA that now trusts hash‑based algorithms.
Collision Resistance – A property of a hash function that makes it comput… #
Collision resistance is essential for the security of Merkle‑tree‑based signatures because a forged authentication path would require a hash collision. Related terms: Preimage Resistance, Second‑Preimage Resistance. Practical note: SHA‑256 and SHA‑3 are widely accepted as collision‑resistant, whereas older functions like MD5 are deprecated.
Commitment Scheme – A protocol that allows one party to commit to a value… #
Some hash‑based signature constructions use commitments to bind the signer to a particular OTS key before revealing the authentication path. Related terms: Binding, Hiding. Example: In a variant of the Winternitz OTS, the signer commits to a random nonce, then later opens the commitment during verification.
Concatenated Hash – The practice of joining multiple hash outputs into a… #
In hash‑based signatures, concatenated hashes may be employed to derive multiple sub‑keys from a master seed. Related terms: Key Derivation Function, Domain Separation. Challenge: Ensuring that concatenation does not introduce unintended correlations that could be exploited by an adversary.
Concurrent Security – A security model that assumes multiple protocol ins… #
Hash‑based signature schemes must be concurrent‑secure to prevent cross‑instance attacks, especially in multi‑threaded environments. Related terms: Session‑Key Separation, Replay Attack. Example: A server handling many TLS handshakes in parallel must keep each XMSS state independent to avoid accidental reuse of one‑time keys.
Crypto‑Agility – The ability of a system to switch cryptographic algorith… #
Hash‑based signatures contribute to crypto‑agility by offering a drop‑in replacement for classical signatures in protocols that abstract the signature primitive. Related terms: Algorithm Negotiation, Versioning. Practical tip: Store both the algorithm identifier and the public key in a versioned structure so that future updates to XMSS or SPHINCS+ can be rolled out seamlessly.
Digital Signature Algorithm (DSA) – A classical public‑key signature sche… #
While DSA is not post‑quantum, it serves as a baseline for comparing performance and security of hash‑based alternatives. Related terms: ECDSA, RSA. Example: A benchmark may report that signing with SPHINCS+ is slower than DSA but offers resistance against quantum attacks.
Domain Separation – A design technique that ensures distinct uses of a ha… #
In hash‑based signatures, domain separation prevents cross‑protocol collisions when the same hash function is reused for key derivation, OTS generation, and Merkle tree construction. Related terms: Context‑Specific Hash, Labeling. Best practice: Use a fixed string such as “XMSS‑KDF” before feeding data into the hash.
Elliptic‑Curve Cryptography (ECC) – A family of algorithms that rely on t… #
Although ECC is efficient, it is vulnerable to Shor’s algorithm, motivating the transition to hash‑based signatures for long‑term security. Related terms: Curve25519, EdDSA. Example: A hybrid scheme may sign a message with both ECDSA and XMSS, providing defense‑in‑depth during the migration period.
Forward Security – A property ensuring that compromise of a current secre… #
Certain hash‑based constructions, such as the stateful XMSS, achieve forward security by never reusing one‑time keys. Related terms: Backward Security, Key Evolution. Practical note: Implementations must carefully manage state to avoid accidental reuse, which would break forward security.
Generalized Merkle Signature Scheme (GMSS) – An extension of the basic Me… #
GMSS is a stateful, hash‑based construction, often compared with LMS and XMSS. Related terms: Layered Tree, Tree Height. Challenge: Managing the complex state across layers without leaking information that could aid an attacker.
Hash Function – A deterministic algorithm that maps arbitrary‑length inpu… #
Secure hash functions underpin all hash‑based signature schemes, providing both compression and randomness. Related terms: SHA‑256, SHA‑3, BLAKE2. Example: In the Winternitz OTS, the signer repeatedly hashes a secret value to generate the public key components.
Hash‑Based Signature (HBS) – A digital signature method that derives its… #
HBS includes one‑time signatures (OTS), many‑time signatures built on Merkle trees, and stateless constructions like SPHINCS+. Related terms: One‑Time Signature, Merkle Tree, Post‑Quantum Cryptography. Practical application: Many governments are evaluating HBS for long‑term document archiving because of its quantum resistance.
Hybrid Signature Scheme – A construction that combines a classical signat… #
The hybrid approach can be used during a transition period. Related terms: Dual‑Signing, Cross‑Compatibility. Example: TLS 1.3 can be configured to send both an ECDSA and an XMSS signature in the CertificateVerify message.
Key Derivation Function (KDF) – A deterministic algorithm that expands a… #
In hash‑based signatures, KDFs are used to generate the many secret seeds required for OTS keys from a single master seed. Related terms: HKDF, PBKDF2. Best practice: Include a domain‑separation tag when invoking the KDF to avoid accidental key reuse across protocol layers.
Key Management – The set of processes for generating, storing, rotating,… #
For stateful hash‑based signatures, key management also involves tracking the index of the next unused OTS key. Related terms: Key Lifecycle, Secure Storage. Challenge: Implementations must guard against “state‑rollback” attacks where an adversary forces the signer to reuse a previously used OTS key.
Lamport One‑Time Signature (Lamport‑OTS) – The earliest known hash‑based… #
Lamport‑OTS is simple but inefficient, requiring large signatures and keys. Related terms: Winternitz OTS, Merkle Tree. Example: A minimal implementation of Lamport‑OTS may be used in constrained devices where code size is more critical than signature length.
Leighton‑Micali Signature (LMS) – A stateful hash‑based many‑time signatu… #
LMS provides fast signing and verification while maintaining post‑quantum security. Related terms: XMSS, GMSS. Practical application: LMS is standardized in RFC 8554 and is employed in certain secure boot loaders for firmware authenticity.
Merkle Authentication Path – The sequence of sibling hashes needed to rec… #
In hash‑based signatures, the authentication path proves that a particular one‑time public key belongs to the signer's Merkle tree. Related terms: Merkle Root, Tree Height. Example: An XMSS signature includes the OTS signature followed by a Merkle authentication path of length equal to the tree height.
Merkle Root – The topmost hash value of a Merkle tree, representing a com… #
The Merkle root is the public key in many hash‑based signature schemes; verification checks that the provided authentication path leads to this root. Related terms: Root Hash, Tree Commitment. In practice, the Merkle root is stored in a certificate or embedded in firmware for later verification.
Message Digest – The output of a hash function applied to a message, ofte… #
The digest is the input to the one‑time signing algorithm in hash‑based signatures. Related terms: Preimage, Collision. Example: When signing a 1 KB file with SPHINCS+, the signer first computes a SHA‑256 digest of the file, then processes that digest through the signature algorithm.
One‑Time Signature (OTS) – A signature scheme that is secure only for a s… #
OTS forms the building block of many hash‑based many‑time schemes. Common OTS variants include Lamport‑OTS, Winternitz‑OTS, and the “few‑time” variants used in XMSS. Related terms: Stateful, Winternitz Parameter. Practical note: Reusing an OTS key destroys the security guarantees, potentially allowing an attacker to recover the secret seed.
Optimistic Signature Verification – A verification approach that first ch… #
In hash‑based signatures, optimistic verification can speed up processing of large batches by discarding obviously invalid signatures early. Related terms: Early Abort, Batch Verification. Example: A server receiving thousands of SPHINCS+ signatures may first compare a short “signature tag” before invoking the full verification routine.
Parameter Set – A collection of algorithmic constants (e #
g., tree height, Winternitz parameter, hash output length) that define a concrete instance of a hash‑based signature scheme. Different parameter sets trade off signature size, key size, and computational cost. Related terms: Security Level, Performance Profile. Example: XMSS‑SHA2‑256‑10 is a parameter set with a 256‑bit hash output and a tree height of 10, yielding about 1024 possible signatures.
Post‑Quantum Cryptography (PQC) – The study and development of cryptograp… #
Hash‑based signatures are a primary category of PQC because their security rests on hash‑function properties, which are not broken by Shor’s algorithm. Related terms: Quantum‑Resistant, NIST PQC Standardization. In practice, organizations may adopt hash‑based signatures for long‑term data integrity, such as archival of legal documents.
Preimage Resistance – The difficulty of finding any input that hashes to… #
Preimage resistance protects against forgery attempts that try to reverse‑engineer a secret OTS seed from its public component. Related terms: Second‑Preimage Resistance, Collision Resistance. Example: An attacker who knows the public key of a Winternitz‑OTS cannot efficiently compute the underlying secret values if the hash function is preimage‑resistant.
Private Key State – In stateful hash‑based signatures, the private key in… #
Maintaining correct state prevents accidental reuse of OTS keys. Related terms: Stateful vs Stateless, Secure Counter. Challenge: Storing the state in non‑volatile memory introduces risks of rollback, which must be mitigated with tamper‑evident hardware or versioned counters.
Quantum Random Oracle Model (QROM) – An extension of the random oracle mo… #
Security proofs for hash‑based signatures are often conducted in the QROM to reflect realistic quantum attack scenarios. Related terms: Random Oracle Model, Indifferentiability. Example: The security reduction for SPHINCS+ is proven in the QROM, showing that breaking the scheme would require a quantum collision‑finding attack on the underlying hash function.
Randomized Signature – A signature that incorporates fresh randomness for… #
Many hash‑based OTS schemes are inherently randomized because each OTS key is unique. Related terms: Nonce, Deterministic Signing. Example: In Lamport‑OTS, the randomness is the secret seed itself; each signature uses a different seed, ensuring randomness without an explicit nonce field.
Replay Attack – An adversary reuses a previously captured valid signature… #
Hash‑based signatures mitigate replay attacks through inclusion of message‑specific data (e.g., timestamps, nonces) in the signed digest. Related terms: Nonce, Freshness. Practical tip: Combine the message hash with a monotonically increasing counter before signing to guarantee uniqueness.
Root Hash – Synonymous with Merkle root; the topmost hash value in a Merk… #
The root hash serves as the public verification key in many hash‑based signature schemes. Related terms: Merkle Root, Tree Commitment. Example: The public key of an LMS instance is the root hash of a Merkle tree constructed over Winternitz OTS public keys.
Secure Hash Algorithm (SHA) – A family of hash functions standardized by… #
SHA‑2 (e.g., SHA‑256) and SHA‑3 (e.g., SHA3‑256) are commonly used in hash‑based signatures due to their proven collision resistance. Related terms: SHA‑256, SHA3‑256. Note: SHA‑1 is deprecated and should never be used in new hash‑based signature deployments.
Signature Aggregation – The process of merging multiple signatures into a… #
While most existing aggregation techniques rely on algebraic groups, research is exploring ways to aggregate hash‑based signatures without sacrificing security. Related terms: Multi‑Signature, Batch Verification. Challenge: Designing an aggregation protocol that respects the one‑time nature of OTS components and does not create cross‑signature leakage.
Signature Size – The number of bytes transmitted as a signature #
Hash‑based signatures typically produce larger signatures than RSA/ECDSA, especially for stateless constructions like SPHINCS+. Related terms: Bandwidth Overhead, Compactness. Example: A 256‑bit security level SPHINCS+ signature may be around 41 KB, whereas an ECDSA‑P256 signature is roughly 64 bytes.
Stateful Signature Scheme – A scheme that requires the signer to maintain… #
g., a leaf index) to guarantee security. XMSS, LMS, and GMSS are examples of stateful hash‑based signatures. Related terms: Stateless, Key Evolution. Practical consideration: Implementations must protect state against loss, duplication, or rollback, often using hardware security modules (HSMs) or trusted execution environments (TEEs).
Stateless Signature Scheme – A construction that does not require the sig… #
SPHINCS+ is a leading stateless hash‑based signature scheme. Related terms: Stateful, FORS. Example: A web service can generate SPHINCS+ signatures on demand without worrying about index synchronization across load‑balanced servers.
Subtree – A portion of a larger Merkle tree, often used in hierarchical c… #
Subtrees enable the signer to precompute authentication paths for future signatures, reducing online computation. Related terms: Layered Tree, Tree Height. Challenge: Managing storage for multiple subtrees while preserving forward security.
Threshold Signature – A scheme where a subset of participants (a threshol… #
While most threshold signatures rely on algebraic groups, researchers are investigating threshold variants of hash‑based signatures, typically by sharing OTS seeds among participants. Related terms: Secret Sharing, Distributed Key Generation. Example: A consortium of data centers could collectively sign a firmware update using a threshold version of LMS.
Timing Attack – A side‑channel attack that extracts secret information by… #
In hash‑based signatures, timing attacks may target the hash computation or the state‑update routine. Related terms: Side‑Channel, Constant‑Time Implementation. Mitigation: Ensure that hash invocations and state increments execute in constant time regardless of input values.
Tree Height – The number of levels from leaf to root in a Merkle tree #
The tree height determines the total number of OTS keys (2^height) that can be safely signed. Related terms: Merkle Tree, Signature Count. Example: An XMSS instance with tree height 16 can produce up to 65,536 signatures before the private key must be regenerated.
Two‑Factor Authentication (2FA) – A security mechanism that requires two… #
Hash‑based signatures can serve as the second factor by signing a challenge nonce, providing strong, quantum‑resistant authentication. Related terms: One‑Time Password, Hardware Token. Practical deployment: A user logs in with a password, then uses a YubiKey that holds an XMSS private key to sign a server‑issued challenge.
Universal One‑Way Function (UOWF) – A function that is easy to compute bu… #
Security proofs for many hash‑based signatures are often expressed in terms of a UOWF. Related terms: One‑Way Function, Hardness Assumption. Example: The underlying hash in SPHINCS+ is treated as a UOWF in the security reduction.
Verifiable Random Function (VRF) – A function that produces a pseudorando… #
VRFs can be combined with hash‑based signatures to generate deterministic, yet unpredictable, nonces. Related terms: Proof of Correctness, Random Oracle. Example: A signer may compute a VRF on the message hash and include the VRF proof inside the signed data to provide auditability.
WOTS+ (Winternitz One‑Time Signature Plus) – An improved version of the W… #
WOTS+ is the OTS component used in many hash‑based many‑time schemes, including XMSS and SPHINCS+. Related terms: Winternitz Parameter, Chain Length. Practical tip: Selecting a larger Winternitz parameter reduces signature size but increases computation; typical values are 16 or 64.
Winternitz Parameter – A integer that controls the trade‑off between sign… #
The parameter determines how many hash iterations are performed per message block. Related terms: WOTS+, Chain Length. Example: With a Winternitz parameter of 16, each message block requires at most 15 hash iterations, leading to moderate signature size and fast computation.
X‑Message Digest (XMD) – A hash‑based expand‑message construction defined… #
XMD is employed in some hash‑based signature schemes for deterministic key derivation. Related terms: Expand‑Message, Hash‑Based KDF. Example: SPHINCS+ may use XMD to derive the many FORS and WOTS+ seeds from a master secret.
XMSS (eXtended Merkle Signature Scheme) – A stateful hash‑based many‑time… #
XMSS combines a Merkle tree with WOTS+ OTS, offering forward security and configurable parameters for various security levels. Related terms: LMS, GMSS, Stateful. Practical usage: XMSS is supported in OpenSSH for post‑quantum key exchange, allowing users to generate long‑term signing keys resistant to quantum attacks.
XMSS‑MT (XMSS Multi‑Tree) – An extension of XMSS that employs multiple Me… #
XMSS‑MT reduces the per‑signature cost of updating state, making it suitable for high‑throughput environments. Related terms: XMSS, Tree Height. Example: A server that must sign millions of messages per day may adopt XMSS‑MT with a moderate tree height per subtree to keep online computation low.
Yao’s Garbled Circuits – A technique for secure two‑party computation tha… #
Though not a signature method itself, garbled circuits may be used to generate proofs that are later signed with a hash‑based scheme. Related terms: Secure Computation, Zero‑Knowledge Proof. Challenge: Integrating garbled circuits with large SPHINCS+ signatures can increase overall bandwidth requirements.
Z‑Parameter (Security Parameter) – The bit length that defines the securi… #
In hash‑based signatures, the Z‑parameter often corresponds to the output length of the underlying hash function (e.g., 256 bits for SHA‑256). Related terms: Security Level, Key Size. Example: Choosing a 384‑bit hash output (SHA‑384) yields a higher Z‑parameter, increasing resistance to quantum attacks at the cost of larger signatures.