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

<< 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.