Post-Quantum Signatures, Part 1: Understanding One-Time Signature

Introduction: Imperative for Quantum-Resistant Signatures

Digital signatures are a cornerstone of modern information security, providing authenticity, integrity, and non-repudiation for digital communications. The security of prevalent schemes such as RSA, DSA, and ECDSA is predicated on the computational hardness of number-theoretic problems—specifically, integer factorization and the discrete logarithm problem. However, the advent of large-scale quantum computers threatens to render these foundations obsolete. Shor's algorithm, a quantum algorithm, can solve both problems in polynomial time, effectively breaking the cryptographic security of a significant portion of our current digital infrastructure.

This imminent threat has catalyzed the field of Post-Quantum Cryptography (PQC), a discipline focused on developing cryptographic systems secure against both classical and quantum adversaries. Among the various families of PQC candidates (lattice-based, code-based, isogeny-based, etc.), Hash-Based Signature (HBS) schemes occupy a unique and trusted position. First conceived in the late 1970s, their security relies not on structured mathematical problems, but on the minimal and well-understood properties of cryptographic hash functions, such as preimage resistance. Given that Grover's quantum search algorithm offers only a quadratic speedup for finding preimages, the security of hash functions is believed to degrade far more gracefully under quantum attacks than that of their number-theoretic counterparts. This property makes HBS a prime candidate for Ethereum's post-quantum roadmap, despite the challenge that it lacks the algebraic structure needed for native BLS-style aggregation.

This reliance on a single, symmetric-key primitive makes HBS schemes particularly attractive from a security assurance perspective. They are built from the ground up on a foundation we understand deeply and trust immensely. The entire edifice of HBS begins with a fundamental, yet seemingly restrictive, concept: One-Time Signature (OTS). Understanding the OTS principle is not merely an academic exercise; it is essential for comprehending the design of nearly all modern hash-based schemes, including the stateful XMSS (eXtended Merkle Signature Scheme) variants relevant to Ethereum's post-quantum roadmap, and the stateless SPHINCS+ standard selected by NIST. In this first post of our series, we will delve into the foundations of OTS: Lamport OTS and Winternitz OTS.

Lamport One-Time Signature Scheme

The Lamport OTS, introduced by Leslie Lamport in 1979, is the archetypal hash-based signature. It provides a direct construction of a signature scheme from any one-way function, which is instantiated in practice with a cryptographic hash function $H$. The scheme is designed to sign a message of a fixed length, say $n$ bits.

Protocol Description

A Lamport OTS scheme consists of three algorithms.

Key Generation

To generate a key pair for an $n$-bit message:

1. The signer generates $n \times 2$ random secret values (secret key), each of length $k$ (e.g., $k=256$ bits). This secret key, $sk$, is structured as two sets of $n$ values: $sk = \{ (sk_{i,0}, sk_{i,1}) \}_{i=1}^{n}$.
2. The public key, $pk$, is derived by applying the hash function $H$ to each secret value: $pk = \{ (pk_{i,0}, pk_{i,1}) \}_{i=1}^{n}$ where $pk_{i,b} = H(sk_{i,b})$ for $b \in \{0,1\}$.

The public key is published, while the secret key is kept private.

Signature Generation

To sign an n$-bit message $m = m_1 m_2 \dots m_n:

1. For each bit $m_i$ of the message, the signer selects the corresponding secret value from the key pair.
2. The signature $\sigma$ is the concatenation of these $n$ selected values: $\sigma = (\sigma_1, \sigma_2, \dots, \sigma_n)$ where $\sigma_i = sk_{i, m_i}$.

Signature Verification

Given the public key $pk$, a message $m$, and a signature $\sigma$:

1. The verifier rederives the message bits $m_1 m_2 \dots m_n$.
2. For each component $\sigma_i$ of the signature, the verifier applies the hash function $H$.
3. The signature is valid if for every $i$ from 1 to $n$, the computed hash matches the corresponding public key element, conditioned on the message bit: $\forall i \in \{1, \dots, n\}: H(\sigma_i) = pk_{i, m_i}$

Security and Limitations

The security of Lamport OTS is directly reducible to the preimage resistance of the hash function $H$. An adversary possessing $pk$ cannot compute any of the $sk_{i,b}$ values, and thus cannot forge a signature for any bit.

The critical limitation is that each key pair is strictly one-time use. After signing a message $m$, the signer reveals half of their secret key. If the same key pair were used to sign a different message $m'$, an adversary could observe the revealed secrets for both signatures. For any bit position $i$ where $m_i \neq m'_i$, the adversary would learn both $sk_{i,0}$ and $sk_{i,1}$.

This knowledge would allow them to substitute either value at will in a future forgery, compromising the security of that bit position permanently. While conceptually foundational, the resulting large key and signature sizes ($2nk$ bits for the public key, and $nk$ bits for the signature) make the original Lamport scheme impractical.

Winternitz OTS

The impracticality of Lamport's scheme, primarily due to its large key and signature sizes, led to a crucial optimization by Robert Winternitz. The core innovation of the Winternitz One-Time Signature (W-OTS) is to trade bits for computation, significantly compacting the signature representation. Instead of a binary choice for each bit, W-OTS processes the message in larger chunks using the elegant mechanism of hash chains.

Core Idea: Signing with Hash Chains

A hash chain of length $k$ on a value $x$ is the sequence $(H^0(x), H^1(x), \dots, H^k(x))$, where $H^0(x)=x$ and the chain progresses via iterative hashing: $H^j(x) = H(H^{j-1}(x))$ for $j>0$.

The W-OTS scheme is parameterized by a security parameter $n$ (the output bit size of the hash function) and a Winternitz parameter $w$, which is a power of 2 (e.g., $w=4, 16, 256$).

Key Generation

1. The message length (typically length of hash digest) and the parameter $w$ determine the number of required hash chains, $l$.
2. The secret key consists of $l$ random n$-bit seeds: $sk = (sk_1, sk_2, \dots, sk_l).
3. The public key is the set of the endpoints of $l$ hash chains, each of length $w-1$, starting from the secret key seeds (initial layer): $pk = (pk_1, pk_2, \dots, pk_l)$ where $pk_i = H^{w-1}(sk_i)$.

Signature Generation

1. The message digest $m$ is converted into a base-$w$ representation, yielding a sequence of chunks $(m_1, \dots, m_{l_1})$, such that $m = \sum_{i=1}^{l_1} m_i *w^{i-1}$ where each $m_i$ is an integer in $\{0, \dots, w-1\}$. This sequence typically includes message chunks and checksum chunks.

2. Crucially, a checksum $C$ is computed as the sum of the "un-traversed" chain lengths for the message part: $C = \sum_{i=1}^{l_1} (w - 1 - m_i)$.
3. This checksum $C$ is then also converted into a base-$w$ representation, yielding $l_2$ checksum chunks $(c_1, \dots, c_{l_2})$ such that $C = \sum_{i=1}^{l_2} c_i *w^{i-1}$ where each $c_i$ is an integer in $\{0, \dots, w-1\}$. The concatenation of message and checksum chunks forms the final codeword, which means $b=M \vert \vert C$, with a length $l = l_1 + l_2$.
4. To sign the chunk b_i$(e.g., $i$-th chunk of the final codeword $b$), the signer reveals an intermediate value from the $i$-th hash chain by hashing the secret $s_i exactly $b_i$ times: $\sigma_i = H^{b_i}(sk_i)$.
5. The full signature $\sigma$ is the concatenation of these $l$ intermediate hash values.

Signature Verification

1. The verifier recomputes the chunks $(b_1, \dots, b_l)$ from the message.
2. For each signature part $\sigma_i$, the verifier continues the hash chain by applying the hash function the remaining number of times, which is $w-1-b_i$.
3. The signature is valid if, for all $i$, this computation reaches the corresponding public key element: $H^{w-1-b_i}(\sigma_i) \stackrel{?}{=} pk_i$. This holds because $H^{w-1-b_i}(H^{b_i}(sk_i)) = H^{w-1}(sk_i) = pk_i$.

W-OTS offers a trade-off: a larger $w$ leads to fewer, but longer, hash chains. This reduces key and signature sizes but increases computational cost. However, the one-time-use constraint remains absolute due to the one-way nature of the chains.

Why Is Checksum Necessary?

The checksum is the component that prevents forgery. After a signature is published, an adversary learns the intermediate value $\sigma_i = H^{b_i}(sk_i)$. From this, they can easily compute any subsequent values on the chain, such as $H^{b_i+1}(sk_i)$. This means an adversary could slightly change a message chunk $b_i$ to a larger value $b'_i > b_i$ and forge the corresponding signature part.

The checksum defeats this attack. If an adversary attempts to increase a message chunk $b_i$ to $b'_i$, the sum of un-traversed lengths for the message part, $\sum (w - 1 - b_j)$, will decrease. This causes the checksum $C$ to decrease. To forge a signature for a smaller checksum value, the adversary would need to reverse one of the checksum's hash chains, which is computationally infeasible due to the preimage resistance of the hash function. Thus, the checksum binds all parts of the signature together, ensuring that no part can be altered without invalidating the whole. This mechanism, however, does not change the scheme's fundamental one-time-use nature.

W-OTS+: Modern Refinement for Stronger Security

While the core idea of W-OTS is powerful, its original formulation had specific security weaknesses. The modern variant used in nearly all contemporary HBS schemes is W-OTS+, introduced by Andreas $\text{H\"{u}lsing}$ in 2013. It strengthens the original design to achieve provable security against stronger adversaries.

The most significant modification in W-OTS+ is the introduction of a family of chain functions through randomized hashing. Instead of a single, simple hash iteration $H(\cdot)$, each step in the chain is "tweaked" with a unique public value.

Let $F$ be a cryptographic hash function and $r = (r_1, r_2, \dots, r_{w-1})$ be a set of public bitmasks. The W-OTS+ chain function is defined as:

$H^0(x, r) = x$, $H^i(x, r) = F(H^{i-1}(x, r) \oplus r_i) \quad \text{for} \quad i > 0$.

Here, $\oplus$ denotes the bitwise XOR operation. Each hashing step is masked with a unique value $r_i$, effectively creating a different hash function for each step in the chain. This prevents attacks that exploit the simple iterative structure of the original W-OTS, such as finding a single hash collision that could be leveraged at multiple points.

The protocol description for W-OTS+ follows the same structure as W-OTS, but replaces the simple chain function $H^k(x)$ with the robust, tweaked version $H^k(x, r)$. For example, verification becomes:

$H^{w-1-b_i}(\sigma_i, (r_{b_i+1}, \dots, r_{w-1})) \stackrel{?}{=} pk_i$

Because of its formal security proof of strong unforgeability under chosen-message attacks (SUF-CMA), W-OTS+ has become the de facto standard for the OTS layer in modern HBS constructions such as XMSS and SPHINCS+. It is this refined version that serves as the foundational building block in the systems we will explore.

OTS As Foundational Building Block

The "one-time" limitation of Lamport and Winternitz schemes makes them unsuitable for direct use in most applications. Their true power lies in their role as a fundamental building block for more complex, multi-use signature schemes.

• Merkle Signature Scheme (MSS): The classical solution to the one-time problem. It uses a Merkle tree to commit to a large number ($2^h$) of OTS public keys. The public key of the MSS is the single root of the tree, and a signature consists of an OTS signature plus an authentication path that proves the OTS key used was part of the tree.
• XMSS and XMSS-MT: These are modern, standardized stateful HBS schemes that refine the MSS design by using W-OTS+ and incorporating optimizations to manage multiple trees (hypertree). They are highly relevant to systems like Ethereum that have an inherent state (e.g., block height or epoch number) that can be used to prevent key reuse.
• SPHINCS+: The stateless HBS scheme selected by NIST for standardization. It constructs a hypertree of trees, where lower-level trees' roots are signed by keys from higher-level trees. At the very bottom of this structure, a few-time signature scheme (FTS) is used, which itself is built from OTS principles.

Conclusion

One-Time Signatures represent the theoretical bedrock of hash-based cryptography. They provide a provably secure signature mechanism with post-quantum resilience, relying only on the minimal assumption of a one-way hash function. While their inherent one-time-use constraint is a significant practical limitation, it is this very limitation that more advanced schemes are designed to overcome. By understanding the elegant mechanics of OTS, we have prepared the ground for our next topic: exploring how Ralph Merkle's ingenious use of a hash tree transformed this disposable primitive into a powerful, multi-use signature scheme: XMSS (eXtended Merkle Signature Scheme).

References

1. Leslie Lamport, 1979: Constructing Digital Signatures from a One Way Function
2. Andreas $\text{H\"{u}lsing}$, 2013: W-OTS+–Shorter Signatures for Hash-based Signature Schemes.
3. Daniel J. Bernstein, Daira Hopwood, Andreas $\text{H\"{u}lsing}$, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O’Hearn, 2015: SPHINCS: Practical Stateless Hash-Based Signatures.
4. National Institute of Standards and Technology, (SPHINCS+/SLH-DSA), 2024: FIPS 205: Stateless Hash-Based Digital Signature Standard.
5. Srivastava, Vikas, Anubhab Baksi and Sumit Kumar Debnath, 2023. An Overview of Hash Based Signatures.
6. Andreas Huelsing, Denis Butin, Stefan-Lukas Gazdag, Joost Rijneveld, Aziz Mohaisen, 2018：RFC 8391, XMSS: eXtended Merkle Signature Scheme.