The Merkle signature scheme is a digital signature scheme based on hash trees (also called Merkle trees) and onetime signatures such as the Lamport signature scheme. It was developed by Ralph Merkle in the late 70s 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 (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 against quantum computing.
Contents
Key generation[edit  edit source]
The Merkle Signature Scheme can only be used to sign a limited number of messages with one public key . The number of possible messages must be a power of two, so that we denote the possible number of messages as .
The first step of generating the public key is to generate the public keys and private keys of onetime signatures. For each private key , with , a hash value is computed. With these hash values a hash tree is built.
We call a node of the tree , where denotes the level of the node. The level of a node is defined by the distance from the node to a leaf. Hence, a leaf of the tree has level and the root has level . We number all nodes of one level from the left to the right, so that is the leftmost node of level .
In the Merkle Tree the hash values are the leafs of a binary tree, so that . Each inner node of the tree is the hash value of the concatenation of its two children. So and . An example of a merkle tree is illustrated in figure \ref{fig:gra1}.
In this way, a tree with leafs and nodes is built. The root of the tree is the public key of the Merkle Signature Scheme.
Signature generation[edit  edit source]
To sign a message with the Merkle Signature Scheme, the message is signed with a onetime signature scheme, resulting in a signature , first. This is done, by using one of the public and private key pairs .
The corresponding leaf of the hash tree to a onetime public key is . We call the path in the hash tree from to the root . The path consists of nodes, , with being the leaf and being the root of the tree. To compute this path , we need every child of the nodes . We know that is a child of . To calculate the next node of the path , we need to know both children of . So we need the brother node of . We call this node , so that . Hence, nodes are needed, to compute every node of the path . We now calculate and save these nodes .
These nodes, plus the onetime signature of is the signature of the Merkle Signature Scheme. An example of an authentication path is illustrated in figure \ref{fig:gra2}.
Signature verification[edit  edit source]
The receiver knows the public key , the message , and the signature . At first, the receiver verifies the onetime signature of the message . If is a valid signature of , the receiver computes by hashing the public key of the onetime signature. For , the nodes of of the path are computed with . If equals the public key of the merkle signature scheme, the signature is valid.
References[edit  edit source]
 G. Becker. "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis", seminar 'Post Quantum Cryptology' at the RuhrUniversity 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. [1]
 S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal merkle tree representation and traversal". RSACT 03, 2003
External links[edit  edit source]
 Efficient Use of Merkle Trees  RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient onetime signature scheme.
