Merkle signature scheme

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
The Merkle Signature Scheme can only 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 that 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} onetime signatures. For each private key Y_{i}, with , a hash value h_{i} = H(Y_{i}) is computed. With these hash values h_{i} a hash tree is built.
We call a node of the tree a_{i,j}, where i 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 i = 0 and the root has level i = n. We number all nodes of one level from the left to the right, so that 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. So a_{1,0} = H(a_{0,0}   a_{0,1}) and a_{2,0} = H(a_{1,0}   a_{1,1}). An example of a merkle tree is illustrated in figure \ref{fig:gra1}.
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
To sign a message M with the Merkle Signature Scheme, the message M is signed with a onetime 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},).
The corresponding leaf of the hash tree to a onetime public key X_{i} is a_{0,i} = H(Y_{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 onetime signature sig' of M is the signature sig = (sig'   auth_{2}   auth_{3}   ...   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 onetime signature sig' of the message M. If sig' is a valid signature of M, the receiver computes A_{0} = H(Y_{i}) by hashing the public key of the onetime 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 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
 Efficient Use of Merkle Trees  RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient onetime signature scheme.
Publickey cryptography Algorithms Benaloh · Blum–Goldwasser · Cayley–Purser · CEILIDH · Cramer–Shoup · Damgård–Jurik · DH · DSA · EPOC · ECDH · ECDSA · EKE · ElGamal (encryption · signature scheme) · GMR · Goldwasser–Micali · HFE · IES · Lamport · McEliece · Merkle–Hellman · MQV · Naccache–Stern · NTRUEncrypt · NTRUSign · Paillier · Rabin · RSA · Okamoto–Uchiyama · Schnorr · Schmidt–Samoa · SPEKE · SRP · STS · Threepass protocol · XTR
Theory Standardization ANS X9F1 · CRYPTREC · IEEE P1363 · NESSIE · NSA Suite B
Topics Digital signature · OAEP · Fingerprint · PKI · Web of trust · Key size
Cryptography Categories: Cryptography
 Asymmetrickey cryptosystems
 Postquantum cryptography
Wikimedia Foundation. 2010.
Look at other dictionaries:
MerkleSignatur — Die Merkle Signatur ist ein digitales Signaturverfahren, das auf Merkle Bäumen sowie Einmalsignaturen wie etwa dem Lamport Einmalsignaturen basiert. Es wurde von Ralph Merkle in den späten Siebzigern entwickelt und stellt eine Alternative zu… … Deutsch Wikipedia
Merkle–Hellman knapsack cryptosystem — The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.[1] Although its ideas are elegant, and far simpler than RSA, it has been broken.[2] Contents 1… … Wikipedia
Merkle–Damgård construction — In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method to build collision resistant cryptographic hash functions from collision resistant one way compression functions.[1]:145 This construction was used in… … Wikipedia
Digital signature — This article is about secure cryptographic signatures. For simple signatures in digital form, see Electronic signature. A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital… … Wikipedia
Lamport signature — In cryptography, a Lamport signature or Lamport one time signature scheme is a method for constructing a digital signature. Lamport signatures can be built from any cryptographically secure one way function; usually a cryptographic hash function… … Wikipedia
Digital Signature Algorithm — The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature… … Wikipedia
Integrated Encryption Scheme — (IES) is a hybrid encryption scheme which provides semantic security against an adversary who is allowed to use chosen plaintext and chosen ciphertext attacks. The security of the scheme is based on the Diffie–Hellman problem. Two incarnations of … Wikipedia
Publickey cryptography — In an asymmetric key encryption scheme, anyone can encrypt messages using the public key, but only the holder of the paired private key can decrypt. Security depends on the secrecy of that private key … Wikipedia
Topics in cryptography — This article is intended to be an analytic glossary , or alternatively, an organized collection of annotated pointers.Classical ciphers*Autokey cipher *Permutation cipher*Polyalphabetic substitution **Vigenère cipher*Polygraphic substitution… … Wikipedia
Diffie–Hellman key exchange — (D–H)[nb 1] is a specific method of exchanging keys. It is one of the earliest practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge … Wikipedia