Merkle signature scheme

The Merkle signature scheme can be used to sign a limited number of messages with one public key $\backslash text\{pub\}$. The number of possible messages must be a power of two, so we denote the possible number of messages as $N\; =\; 2^n$.

The first step of generating the public key $\backslash text\{pub\}$ is to generate $N$ private/public key pairs $(X\_i,\; Y\_i)$ of some one-time signature scheme (such as the Lamport signature scheme). For each $1\; \backslash leq\; i\; \backslash leq\; 2^n$, a hash value of the public key $h\_i\; =\; H(Y\_i)$ is computed.

Image:MerkleTree1.1.svg

With these hash values $h\_i$ a hash tree is built, by placing these $2^n$ hash values as leaves and recursively hashing to form a binary tree. Let $a\_\{i,j\}$ denote the node in the tree with height $i$ and left-right position $j$. Then, the hash values $h\_i\; =\; a\_\{0,i\}$ are the leaves. The value for each inner node of the tree is the hash of the concatenation of its two children. For example, $a\_\{1,0\}\; =\; H(a\_\{0,0\}\; ||\; a\_\{0,1\})$ and $a\_\{2,0\}\; =\; H(a\_\{1,0\}\; ||\; a\_\{1,1\})$. In this way, a tree with $2^n$ leaves and $2^\{n+1\}\; -\; 1$ nodes is built.

The private key of the Merkle signature scheme is the entire set of $(X\_i,\; Y\_i)$ pairs. A shortcoming with the scheme is that the size of the private key scales linearly with the number of messages to be sent.

The public key $\backslash text\{pub\}$ is the root of the tree, $a\_\{n,0\}$. The individual public keys $Y\_i$ can be made public without breaking security. However, they are not needed in the public key, so they can be kept secret to minimize the size of the public key.

To sign a message $M$ with the Merkle signature scheme, the signer picks a key pair $(X\_i,\; Y\_i)$, signs the message using the one-time signature scheme, and then adds additional information to prove that the key pair used was one of the original key pairs (rather than one newly generated by a forger).

Image:MerkleTree2.1.svg

First, the signer chooses a $(X\_i,\; Y\_i)$ pair which had not previously been used to sign any other message, and uses the one-time signature scheme to sign the message, resulting in a signature $\backslash text\{sig\}\text{'}$ and corresponding public key $Y\_i$. To prove to the message verifier that $(X\_i,\; Y\_i)$ was in fact one of the original key pairs, the signer simply includes intermediate nodes of the Merkle tree so that the verifier can verify $h\_i\; =\; a\_\{0,i\}$ was used to compute the public key $a\_\{n,0\}$ at the root of the tree. The path in the hash tree from $a\_\{0,i\}$ to the root is $n\; +\; 1$ nodes long. Call the nodes $A\_0,\; \backslash ldots,\; A\_n$, with $A\_0\; =\; a\_\{0,i\}\; =\; H(Y\_i)$ being a leaf and $A\_n\; =\; a\_\{n,0\}\; =\; \backslash text\{pub\}$ being the root.

$A\_i$ is a child of $A\_\{i+1\}$. To let the verifier calculate the next node $A\_\{i+1\}$ given the previous, they need to know the other child of $A\_\{i+1\}$, the sibling node of $A\_i$. We call this node $\backslash text\{auth\}\_i$, so that $A\_\{i+1\}\; =\; H(A\_i\; ||\; \backslash text\{auth\}\_i)$. Hence, $n$ nodes $\backslash text\{auth\}\_0,\; \backslash ldots,\; \backslash text\{auth\}\_\{n-1\}$ are needed, to reconstruct $A\_n\; =\; a\_\{n,0\}\; =\; \backslash text\{pub\}$ from $A\_0\; =\; a\_\{0,i\}$. An example of an authentication path is illustrated in the figure on the right.

Together, the nodes $\backslash text\{auth\}\_\{0\},\; \backslash ldots,\; \backslash text\{auth\}\_\{n-1\}$, the $Y\_i$, and the one-time signature $\backslash text\{sig\}\text{'}$ constitute a signature of $M$ using the Merkle signature scheme: $\backslash text\{sig\}\; =\; (\backslash text\{sig\}\text{'}\; ||\; Y\_i\; ||\; \backslash text\{auth\}\_0\; ||\; \backslash text\{auth\}\_1\; ||\; \backslash ldots\; ||\; \backslash text\{auth\}\_\{n-1\})$.

Note that when using the Lamport signature scheme as the one-time signature scheme, $\backslash text\{sig\}\text{'}$ contains a part of the private key $X\_i$.

The receiver knows the public key $\backslash text\{pub\}$, the message $M$, and the signature $\backslash text\{sig\}\; =\; (\backslash text\{sig\}\text{'}\; ||\; Y\_i\; ||\; \backslash text\{auth\}\_0\; ||\; \backslash text\{auth\}\_1\; ||\; \backslash ldots\; ||\; \backslash text\{auth\}\_\{n-1\})$. First, the receiver verifies the one-time signature $\backslash text\{sig\}\text{'}$ of the message $M$ using the one-time signature public key $Y\_i$. If $\backslash text\{sig\}\text{'}$ is a valid signature of $M$, the receiver computes $A\_0\; =\; H(Y\_i)$ by hashing the public key of the one-time signature. For $j\; =\; 1,\; \backslash ldots,\; n\; -\; 1$, the nodes of $A\_j$ of the path are computed with $A\_j\; =\; H(A\_\{j-1\}\; ||\; \backslash text\{auth\}\_\{j-1\})$. If $A\_n$ equals the public key $\backslash text\{pub\}$ of the Merkle signature scheme, the signature is valid.

{{reflist|1}}

• E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, L.C. Coronado Garca. "CMSS - an improved merkle signature scheme". Progress in Cryptology – Indocrypt 2006, 2006.
• E. Klintsevich, K. Okeya, C.Vuillaume, J. Buchmann, E.Dahmen. "Merkle signatures with virtually unlimited signature capacity". 5th International Conference on Applied Cryptography and Network Security - ACNS07, 2007.
• M. Jakobsson, T. Leighton, S. Micali, M. Szydlo. "Fractal Merkle tree representation and traversal". RSA-CT 03, 2003

• [http://www.emc.com/emc-plus/rsa-labs/historical/recent-improvements-efficient-use-merkle-trees.htm Efficient Use of Merkle Trees] - RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient one-time signature scheme.
• [https://www.imperialviolet.org/2013/07/18/hashsig.html An introduction to hash-based signatures and Merkle signatures by Adam Langley.]
• [https://www.cryptologie.net/article/306/one-time-signatures/ A 4 parts series on hash-based signatures by David Wong.]

{{Cryptography navbox | public-key}}

{{Authority control}}

{{Use dmy dates|date=February 2025}}

Category:Digital signature schemes

Category:Hash-based cryptography

Category:Post-quantum cryptography

Category:Public-key cryptography