In hash-based cryptography, the Merkle signature scheme is a digital signature scheme based on Merkle trees (also called hash 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. NIST has approved specific variants of the Merkle signature scheme in 2020. An advantage of the Merkle signature scheme is that it is believed to be resistant against attacks by quantum computers. The traditional public key algorithms, such as RSA and ElGamal would become insecure if an effective quantum computer could 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 computer-based attacks. The Merkle signature is a one time signature with finite signing potential. The work of Moni Naor and Moti Yung on signature based one-way permutations and functions (and the invention of universal one-way hash functions) gives a way to extend a Merkle-like signature to a complete signature scheme.
Key generation The Merkle signature scheme can be used to sign a limited number of messages with one public key pub {\displaystyle {\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 {\displaystyle N=2^{n}} . The first step of generating the public key pub {\displaystyle {\text{pub}}} is to generate N {\displaystyle N} private/public key pairs ( X i , Y i ) {\displaystyle (X_{i},Y_{i})} of some one-time signature scheme (such as the Lamport signature scheme). For each 1 ≤ i ≤ 2 n {\displaystyle 1\leq i\leq 2^{n}} , a hash value of the public key h i = H ( Y i ) {\displaystyle h_{i}=H(Y_{i})} is computed.
With these hash values h i {\displaystyle h_{i}} a hash tree is built, by placing these 2 n {\displaystyle 2^{n}} hash values as leaves and recursively hashing to form a binary tree. Let a i , j {\displaystyle a_{i,j}} denote the node in the tree with height i {\displaystyle i} and left-right position j {\displaystyle j} . Then, the hash values h i = a 0 , i {\displaystyle 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 ) {\displaystyle a_{1,0}=H(a_{0,0}||a_{0,1})} and a 2 , 0 = H ( a 1 , 0 | | a 1 , 1 ) {\displaystyle a_{2,0}=H(a_{1,0}||a_{1,1})} . In this way, a tree with 2 n {\displaystyle 2^{n}} leaves and 2 n + 1 − 1 {\displaystyle 2^{n+1}-1} nodes is built. The private key of the Merkle signature scheme is the entire set of ( X i , Y i ) {\displaystyle (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 pub {\displaystyle {\text{pub}}} is the root of the tree, a n , 0 {\displaystyle a_{n,0}} . The individual public keys Y i {\displaystyle 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.
… excerpt ends here. Continue reading the full article.
