Basic Merkle Signature Scheme
We can use the Merkle tree construction to generate N onetime signatures. We call this an Ntime OTS scheme.
Parameters
m = length of message (digest) to be signed k = security parameter h = hash function with kbit output
Key generation
Let $K_s^{(i)}$ denote the secret key of the $i$th onetime 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.

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.

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_1X_2\ldotsX_mY_1Y_2\ldotsY_m$
 and then compute the hash value over this for its parent node in the tree.

Build the nodes of the Merkle tree
node = h(leftchild  rightchild)
, where each node contains one $k$bit hash value.

Publish the $k$bit value at the root node as the public key for this $N$time scheme.
Create a signature

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

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

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

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

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 previouslyused 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))$
<< previous: Merkle Tree  Contents  next: Few Time Signature (FTS) >> 
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 17 March 2023.