Merkle signature scheme

The Merkle signature scheme is a digital signature scheme based on hash trees (also called Merkle trees) and one-time signatures such as the Lamport signature scheme. It was developed by Ralph Merkle in the late 1970s and is an alternative to traditional digital signatures such as the Digital Signature Algorithm or RSA.

The advantage of the Merkle Signature Scheme is that it is believed to be resistant against quantum computer algorithms. The traditional public key algorithms, such as RSA and ELGamal would become insecure in case an effective quantum computer can be built (due to Shor's algorithm). The Merkle Signature Scheme however only depends on the existence of secure hash functions. This makes the Merkle Signature Scheme very adjustable and resistant to quantum computing.

Key generation

Merkle Tree with 8 leaves

The Merkle Signature Scheme can be used to sign a limited number of messages with one public key $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 $pub$ is to generate the public keys $X_i$ and private keys $Y_i$ of $2^n$ one-time signatures. For each public key $X_i$ , with $1 \leq i \leq 2^n$ , a hash value $h_i=X_i=H(Y_i)$ is computed. With these hash values $h_i$ a hash tree is built.

Each node of the tree is represented as $a_{i,j}$ , where $i$ denotes the height of the node and $j$ denotes the left-to-right position of the node. The height of a node is defined as the distance from the node to a leaf. Hence, a leaf of the tree has height $i=0$ and the root has height $i=n$ . Nodes with the same height are numbered from left to right, so $a_{i,0}$ is the leftmost node of level $i$ .

In the Merkle Tree the hash values $h_i$ are the leaves of a binary tree, so that $h_i=a_{0,i}$ . Each inner node of the tree is the hash value 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 root of the tree, $a_{n,0}$ , is the public key $pub$ of the Merkle Signature Scheme.

Signature generation

Merkle tree with path A and authentication path for i=2

To sign a message $M$ with the Merkle Signature Scheme, the message $M$ is signed with a one-time signature scheme, resulting in a signature $sig'$ , first. This is done, by using one of the public and private key pairs $(X_i, Y_i,)$ . [Need to define computation of $sig'$ ]

The corresponding leaf of the hash tree to a one-time public key $X_i$ is $a_{0,i}=H(X_i)$ . We call the path in the hash tree from $a_{0,i}$ to the root $A$ . The path $A$ consists of $n+1$ nodes, $A_0, ... A_n$ , with $A_0=a_{0,i}$ being the leaf and $A_n=a_{n,0}=pub$ being the root of the tree. To compute this path $A$ , we need every child of the nodes $A_{1}, ..., A_{n}$ . We know that $A_i$ is a child of $A_{i+1}$ . To calculate the next node $A_{i+1}$ of the path $A$ , we need to know both children of $A_{i+1}$ . So we need the brother node of $A_i$ . We call this node $auth_i$ , so that $A_{i+1}=H(A_i||auth_i)$ . Hence, $n$ nodes $auth_0,...,auth_{n-1}$ are needed, to compute every node of the path $A$ . We now calculate and save these nodes $auth_{0}, ... , auth_{n-1}$ .

These nodes, plus the one-time signature $sig'$ of $M$ is the signature $sig=(sig'||auth_0||auth_1||...||auth_{n-1})$ of the Merkle Signature Scheme. An example of an authentication path is illustrated in the figure on the right.

Signature verification

The receiver knows the public key $pub$ , the message $M$ , and the signature $sig=(sig'||auth_0||auth_1||...||auth_{n-1})$ . At first, the receiver verifies the one-time signature $sig'$ of the message $M$ . If $sig'$ is a valid signature of $M$ , the receiver computes $A_0=H(X_i)$ by hashing the public key of the one-time signature. For $j=1,..,n-1$ , the nodes of $A_j$ of the path $A$ are computed with $A_j=H(A_{j-1}||auth_{j-1})$ . If $A_n$ equals the public key $pub$ of the merkle signature scheme, the signature is valid.

References

G. Becker. "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis", seminar 'Post Quantum Cryptology' at the Ruhr-University Bochum, Germany.
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.
Ralph Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979.
S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal merkle tree representation and traversal". RSA-CT 03, 2003

External links

Efficient Use of Merkle Trees - RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient one-time signature scheme.

Public-key cryptography

Algorithms	Benaloh Blum–Goldwasser Cayley–Purser CEILIDH Cramer–Shoup Damgård–Jurik DH DSA EPOC ECDH ECDSA EdDSA EKE ElGamal signature scheme GMR Goldwasser–Micali HFE IES Lamport McEliece Merkle–Hellman MQV Naccache–Stern Naccache–Stern knapsack cryptosystem NTRUEncrypt NTRUSign Paillier Rabin RSA Okamoto–Uchiyama Schnorr Schmidt–Samoa SPEKE SRP STS Three-pass protocol XTR

Theory	Discrete logarithm Elliptic curve cryptography Non-commutative cryptography RSA problem

Standardization	CRYPTREC IEEE P1363 NESSIE NSA Suite B

Topics	Digital signature OAEP Fingerprint PKI Web of trust Key size

Cryptography

History of cryptography Cryptanalysis Cryptography portal Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography