Wots

Winternitz One-Time Signature (WOTS) is a hash-based digital signature scheme designed for signing a single message with high efficiency. Introduced by Sergei Winternitz in 1984, WOTS is a foundational building block in post-quantum cryptography due to its reliance on hash function preimage resistance rather than algebraic hardness assumptions.

In WOTS, the private key consists of a sequence of secret values. The public key is generated by applying a cryptographic hash function to each secret value a fixed number of times, known as the chain length. To sign a message, the message is first hashed and then encoded into a set of digits in a chosen base, along with a checksum. Each digit determines how many times the corresponding secret value’s hash is iterated to produce a signature component. The full signature is a collection of these hash outputs. Verification replays the same hash iterations from the public key components to confirm consistency with the signature and the message.

Security relies on the one-way nature of the hash function; a key must be used for signing at most one message, because reusing the private key exposes additional attack vectors on the hash chains. WOTS parameters trade off signature size, key size, and computation via the Winternitz parameter w, with common choices yielding l1 = ceil(n / log2 w) and l2 = floor(log2(l1*(w-1))/log2 w) + 1, for a total length l = l1 + l2.

Variants such as WOTS+ refine the scheme for improved security properties and performance. WOTS is widely employed as a building block in hash-based, post-quantum signature schemes like XMSS, XMSSMT, and SPHINCS+.