Winternitz One-Time Signature Scheme (W-OTS)

The W-OTS scheme follows the Lamport signature approach but allows a signer to sign w bits of a message-digest simultaneously rather than 1. This collection of bits is a treated as a "digit" of base 2^w.

For example, in the case of w=8 the digits simply become bytes since each digit can take any value within 0..255. The fundamental cryptographic mechanism in W-OTS is the ability to sign individual digits using a unique "digit private key".

For example, to sign the byte b (for w=8), a signer first derives a "private digit key" as K = H(secret) and a "public digit key" P = H^255(K). Notice that all the values of b map to a unique hash in that chain of hashes. The signer advertises the "public digit key" prior to signing any digit. When signing a digit b, the signer provides the verifier the value S=H^(255-b)(K) referred to as the "signature of b". The verifier need only perform b more iterations on the signature s to arrive at the public key P, since H^b(S) = H^b(H^(255-b)(K)) = H^255(K) = P.

At this point, the verifier has cryptographically determined the signer had knowledge of K since the signature S was the b'th pre-image of P. This process of signing digits is repeated for each digit in the message and each digit signature is concatenated to form the signature. The message being signed is always a digest of an actual logical message, and thus referred to as the "message-digest".

In W-OTS, the individual "digit keys" and "digit signatures" are concatenated to comprise the "key" and "signatures" respectively. This results in order of magnitude larger key and signature objects when compared to traditional elliptic-curve / discrete logarithm schemes. This is a significant down-side of OTS schemes when used in post-quantum cryptography (PQC) use cases. The burden of large keys can be optimized by using the hash of a public key as WAMSD prescribes. The burden of large signatures can be halved by choosing shorter hash functions without impacting security, as prescribed by the W-OTS#4 variant. .

ℹī¸ In order to prevent signature forgeries arising from digit signature re-use for prior messages, a checksum is calculated and appended to the message-digest and co-signed. The checksum is calculated in such a way that any increment to a message digit necessarily decreases a checksum digit. Thus it is impossible to forge a signature since it requires the pre-image of at least one checksum digit signature.