- 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 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 = 2n.
The first step of generating the public key pub is to generate the public keys Xi and private keys Yi of 2n one-time signatures. For each private key Yi, with , a hash value hi = H(Yi) is computed. With these hash values hi a hash tree is built.
We call a node of the tree ai,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 ai,0 is the leftmost node of level i.
In the Merkle Tree the hash values hi are the leaves of a binary tree, so that hi = a0,i. Each inner node of the tree is the hash value of the concatenation of its two children. So a1,0 = H(a0,0 | | a0,1) and a2,0 = H(a1,0 | | a1,1). An example of a merkle tree is illustrated in figure \ref{fig:gra1}.
In this way, a tree with 2n leaves and 2n + 1 − 1 nodes is built. The root of the tree an,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 one-time signature scheme, resulting in a signature sig', first. This is done, by using one of the public and private key pairs (Xi,Yi,).
The corresponding leaf of the hash tree to a one-time public key Xi is a0,i = H(Yi). We call the path in the hash tree from a0,i to the root A. The path A consists of n + 1 nodes, A0,...An, with A0 = a0,i being the leaf and An = an,0 = pub being the root of the tree. To compute this path A, we need every child of the nodes A1,...,An. We know that Ai is a child of Ai + 1. To calculate the next node Ai + 1 of the path A, we need to know both children of Ai + 1. So we need the brother node of Ai. We call this node authi, so that Ai + 1 = H(Ai | | authi). Hence, n nodes auth0,...,authn − 1 are needed, to compute every node of the path A. We now calculate and save these nodes auth0,...,authn − 1.
These nodes, plus the one-time signature sig' of M is the signature sig = (sig' | | auth2 | | auth3 | | ... | | authn − 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' | | auth0 | | auth1 | | ... | | authn − 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 A0 = H(Yi) by hashing the public key of the one-time signature. For j = 1,..,n − 1, the nodes of Aj of the path A are computed with Aj = H(Aj − 1 | | authj − 1). If An 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. [1]
- 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 · 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 · Three-pass 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
- Asymmetric-key cryptosystems
- Post-quantum cryptography
Wikimedia Foundation. 2010.