DI Management Home > Cryptography > SPHINCS+ > Basic Merkle Signature Scheme

# 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.
 << previous: Merkle Tree Contents next: Few Time Signature (FTS) >>