Basic Merkle Signature Scheme

We can use the Merkle tree construction to generate N one-time signatures. We call this an N-time OTS scheme.

Parameters

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

Key generation

Let $K_s^{(i)}$ denote the secret key of the $i$th one-time scheme for $1\le i\le N$, where $K_s$ is as defined in Alternative Summary of Lamport OTS Scheme. $N$ should be a power of 2.

1. Generate $N$ sets of private signing keys $K_s^{(1)}, K_s^{(2)},\ldots K_s^{(N)}$, where each key $K_s^{(i)}$ consists of $2m$ $k$-bit secret values.

2. Set up an $N$-leaf Merkle tree with the leaves being the corresponding public key values $K_p^{(i)}$

   • if $K_s = A_1 \ldots A_m, B_1\ldots B_m$ then $K_p = X_1 \ldots X_m, Y_1\ldots Y_m$ where $X_i = h(A_1)$ and $Y_i=h(B_i)$.
   • One efficient way to store the public key $K_p$ is as the $2mk$ bit string
     • $X_1||X_2||\ldots||X_m||Y_1||Y_2||\ldots||Y_m$
     • and then compute the hash value over this for its parent node in the tree.

3. Build the nodes of the Merkle tree

   • node = h(leftchild || rightchild), where each node contains one $k$-bit hash value.

4. Publish the $k$-bit value at the root node as the public key for this $N$-time scheme.

Create a signature

1. Let $i$ denote the number of signatures performed previously by the owner of the tree, starting at $i=0$.

2. Use the private key $K_s^{(i)}$ to sign the message (digest) $M$ giving the signature $S=S_1, S_2, \ldots, S_m$.

3. Output the signature over $M$ consisting of

   • $S$ as computed in step 2
   • $i$
   • the public key $K_p^{(i)}$
   • the authentication path from the leaf in the Merkle tree with $K_p^{(i)}$

Verification

1. Use the public key $K_p^{(i)}$ to verify the one-time signature $S$ over the message $M$.

2. Check that the authentication path is valid and results in the published root value.

Important

This is a stateful scheme. The owner must keep track of the number of signatures performed using the tree and must never use a previously-used key. To do so can destroy the security of the scheme.

Generating private keys using a seed

• You could generate $N$ sets of $2m$ $k$-bit random values for the private key $K_s$ and store them all.
• Alternatively, you can generate a secret $k$-bit random SEED and use this with a hash function to generate the private key values each time. A simple example might be:
  • $A_i = h(\text{SEED}, \text{toBytes}(0), \text{toBytes}(i))$
  • $B_i = h(\text{SEED}, \text{toBytes}(1), \text{toBytes}(i))$
  where $\text{toBytes}(i)$ converts an integer $i$ into a byte array.

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 9 September 2025.