One-time signature (OTS) scheme

A one-time signature (OTS) scheme based on a one-way function was first introduced by Lamport [LAM79] in 1979. It is known as the Lamport OTS or Lamport-Diffie OTS. The description by Merkle [MER79] is probably clearer.

It requires a one-way cryptographic hash function, $H()$, for example SHA-256. It is a one-time scheme, so as per the label on the can, a given private-public key pair can only be used once.

Lamport One Time Signature for a single bit message
Lamport OTS for a message of any length
Alternative Summary of Lamport OTS Scheme

Lamport One Time Signature for a single bit message

First, consider a simple Lamport scheme to sign a message of just one bit (0 or 1).

• Select two distinct values $x$ and $y$ as your private key.
• Compute $H(x)$ and $H(y)$ and publish these as your public key.
• To sign the bit 0, reveal $x$. To sign the bit 1, reveal $y$.
• To verify, for example, the message bit 1 signed using $y'$, compute $H(y')$ and check that this matches the published value $H(y)$.
• To forge a signature over the message bit 0, a forger needs to compute the value of $x$ from the public $H(x)$. This is infeasible for a secure one-way hash function.

Lamport OTS for a message of any length

• To use this scheme to sign a message, $M$, of any length, use a cryptographic hash function to compress the message to a fixed number of bits.
  • for example, use SHA-256 to compute a message digest of 256 bits, $md=\text{SHA-256}(M) = b_0b_1\ldots b_{255}$
  • note that some authors use $M$ to represent the fixed-length message digest (as we will do later!).
• Generate a private key of 256 distinct random key pairs $(x,y)$
  • $(x_0,y_0), (x_1,y_1), \ldots, (x_{255},y_{255})$
• Publish your public key as the hashes of these 512 values
  • $(H(x_0),H(y_0)), (H(x_1),H(y_1)), \ldots, (H(x_{255}),H(y_{255}))$
• To sign, for each bit in the message digest, $md = b_0b_1\ldots b_{255}$, reveal either $x_i$ or $y_i$ depending on whether the message bit $b_i$ is 0 or 1.
  • thus the signature will consist of an array of 256 digest values, each 32 bytes long.
• To verify, compute your own 256-bit message digest $md$ of the message and check each bit $b_i$ against the published $H(x_i)$ or $H(y_i)$.
• Disadvantage: Each SHA-256 hash value is 32 bytes long and we have 256 pairs of hash values in the public key, so it's 16 kB long!

For an excellent alternative explanation of this (with great diagrams), see [WONG15]

Alternative Summary of Lamport OTS Scheme

An alternative summary of the Lamport OTS Scheme described in [LEI95]. We will use syntax this later in Basic Merkle Signature Scheme.

m = length of message (digest) to be signed
k = security parameter
h = hash function with k-bit output

• The secret signing key $K_s$ consists of $2m$ randomly-generated strings $A_1, \ldots, A_m$, $B_1, \ldots,B_m$, each of $k$ bits.
• The corresponding public verification key $K_p$ consists of $X_1, \ldots, X_m$, $Y_1, \ldots,Y_m$, where $X_i= h(A_i)$ and $Y_i= h(B_i)$ for $1\le i \le m$.
• The signature of an $m$-bit message $M=b_1\ldots b_m$ consists of $S_1,S_2,\ldots ,S_m$ where $S_i=A_i$ if $b_i = 0$ or $S_i=B_i$ if $b_i=1$.
• The signature is verified by checking that $h(S_i)=X_i$ if $b_i = 0$ or $h(S_i)=Y_i$ if $b_i=1$.

Chinese translation

Zhanglu Wang has kindly translated this page to Chinese on the CSDN site 一次性签名 (OTS) 方案. Thank you Wang.

Rate this page

Contact us

To comment on this page or to contact us, please send us a message.

This page first published 17 March 2023. Last updated 30 August 2026.