Merkle signature

The Merkle signature is a digital signature method based on Merkle trees and one-time signatures such as the Lamport one-time signatures . It was developed by Ralph Merkle in the late 1970s and represents an alternative to traditional digital signatures such as the Digital Signature Algorithm or RSA- based signatures. In contrast to these, it is resistant to attacks by quantum computers , since its security only depends on its existence more secure hash functions .

idea

One problem with one-time signatures such as the Lamport signature is the transmission of the public key. Since each key can only be used once, there is a large amount of data that has to be reliably passed on to the recipient.

The Merkle signature process solves this problem by combining the entire (public) key material of one-time signatures in a multi-level hash process into a single hash value . As a public key, it only needs to be published, then messages can be signed with it . ${\displaystyle 2^{n}}$ ${\displaystyle pub}$ ${\displaystyle pub}$ ${\displaystyle 2^{n}}$

The signature of a message then consists of two parts:

• One of the public keys and the message signed with the corresponding private key. The recipient can verify that the sender actually had the private key. ${\displaystyle 2^{n}}$
• Proof that the public key is one of the keys from which the hash value was calculated. ${\displaystyle 2^{n}}$ ${\displaystyle pub}$

Key generation

Merkle tree with 8 leaves

The Merkle signature process can only be used to sign a limited number of messages with a public key . The number of possible messages is a power of two and is therefore referred to as . ${\displaystyle pub}$ ${\displaystyle N=2^{n}}$

The first step in generating the public key is generating the private key and the public key from one-time signatures. A hash value is calculated for each public key with . A hash tree is built with these hash values . ${\displaystyle pub}$ ${\displaystyle X_{i}}$ ${\displaystyle Y_{i}}$ ${\displaystyle 2^{n}}$ ${\displaystyle Y_{i}}$ ${\displaystyle 1\leq i\leq 2^{n}}$ ${\displaystyle h_{i}=H(Y_{i})}$ ${\displaystyle h_{i}}$

A node of the tree is identified with , where denotes the level of the node. The level of a node is defined by its distance from the leaves. Thus a leaf has the plane and the root has the plane . The nodes of each level are numbered from left to right so that the leftmost node is on level . ${\displaystyle a_{i,j}}$ ${\displaystyle i}$ ${\displaystyle i=0}$ ${\displaystyle i=n}$ ${\displaystyle a_{i,0}}$ ${\displaystyle i}$

In the Merkle tree, the hash values ​​are the leaves of the binary tree, so . Each inner node of the tree is the hash value of the concatenation of its two children. For example, is and . ${\displaystyle h_{i}}$ ${\displaystyle h_{i}=a_{0,i}}$ ${\displaystyle a_{1,0}=H(a_{0,0}||a_{0,1})}$ ${\displaystyle a_{2,0}=H(a_{1,0}||a_{1,1})}$

In this way a tree is built with leaves and nodes. The root of the tree is the public key of the Merkle signature process. ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n+1}-1}$ ${\displaystyle a_{n,0}}$ ${\displaystyle pub}$

signing

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

To sign a message with the Merkle signature process, the message is first signed with a one-time signature process , which creates the signature . One of the key pairs from the private and public key is used for this. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle sig'}$ ${\displaystyle (X_{i},Y_{i},)}$

The leaf of the hash tree associated with a private one-time key is . The path in the hash tree from to the root is denoted by. The path is made up of nodes, where the leaves are and the root is the tree. Each node child is required to calculate this path . It is known that a child is. In order to compute the next node of the path , both children of must be known. Hence, the brother of is needed. This node is labeled so that . Therefore nodes are needed to compute every node of the path . These nodes are calculated and saved. Together with a one-time signature from, they form the signature of the Merkle signature process. ${\displaystyle X_{i}}$ ${\displaystyle a_{0,i}=H(Y_{i})}$ ${\displaystyle a_{0,i}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n+1}$ ${\displaystyle A_{0},\ldots ,A_{n}}$ ${\displaystyle A_{0}=a_{0,i}}$ ${\displaystyle A_{n}=a_{n,0}=pub}$ ${\displaystyle A}$ ${\displaystyle A_{1},\ldots ,A_{n}}$ ${\displaystyle A_{i}}$ ${\displaystyle A_{i+1}}$ ${\displaystyle A_{i+1}}$ ${\displaystyle A}$ ${\displaystyle A_{i+1}}$ ${\displaystyle A_{i}}$ ${\displaystyle auth_{i}}$ ${\displaystyle A_{i+1}=H(A_{i}||auth_{i})}$ ${\displaystyle n}$ ${\displaystyle auth_{0},\ldots ,auth_{n-1}}$ ${\displaystyle A}$ ${\displaystyle auth_{0},\ldots ,auth_{n-1}}$ ${\displaystyle sig'}$ ${\displaystyle M}$ ${\displaystyle sig=(sig',auth_{0},auth_{1},\ldots ,auth_{n-1})}$

verification

The recipient knows the public key , the message , and the signature . First, the recipient verifies the one-time signature of the message . If is a valid signature from , the receiver calculates by calculating the hash value of the public key of the one-time signature. The nodes of the path are calculated for with . If the public key corresponds to the Merkle signature process, the signature is valid. ${\displaystyle pub}$ ${\displaystyle M}$ ${\displaystyle sig=(sig',auth_{0},auth_{1},\ldots ,auth_{n-1})}$ ${\displaystyle sig'}$ ${\displaystyle M}$ ${\displaystyle sig'}$ ${\displaystyle M}$ ${\displaystyle A_{0}=H(Y_{i})}$ ${\displaystyle j=1,..,n-1}$ ${\displaystyle A_{j}}$ ${\displaystyle A}$ ${\displaystyle A_{j}=H(a_{j-1}||b_{j-1})}$ ${\displaystyle A_{n}}$ ${\displaystyle pub}$

Further developments

In the course of the search for quantum computer-resistant signature processes, the process has recently come back into focus. In the meantime, improved variants of the Merkle signature procedure have been published, including a.

• XMSS (eXtended Merkle Signature Scheme), which was standardized as RFC 8391 in 2018
• SPHINCS with larger signatures than XMSS, but stateless

swell

• G. Becker: Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis (PDF file; 370 kB), seminar 'Post Quantum Cryptology' at the Ruhr University Bochum .
• E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, LC Coronado Garca: CMSS - an improved merkle signature scheme (PDF file; 264 kB). Progress in Cryptology - Indocrypt 2006, 2006.
• E. Klintsevich, K. Okeya, C. Vuillaume, J. Buchmann, E. Dahmen: Merkle signatures with virtually unlimited signature capacity (PDF file; 179 kB). 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. ( PDF )
• Silvio Micali , M. Jakobsson, T. Leighton, M. Szydlo: Fractal merkle tree representation and traversal . RSA-CT 03, 2003

1. ^ Johannes Buchmann, Erik Dahmen, Andreas Hülsing: XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions . In: Post-Quantum Cryptography. PQCrypto 2011 (=  Lecture Notes in Computer Science . Volume 7071 ). Springer, Berlin Heidelberg 2011, p. 117-129 , doi : 10.1007 / 978-3-642-25405-5_8 .
2. ^ Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, Zooko Wilcox-O'Hearn: SPHINCS: practical stateless hash-based signatures . In: Elisabeth Oswald, Marc Fischlin (Ed.): Advances in Cryptology - EUROCRYPT 2015 (=  Lecture Notes in Computer Science . Volume 9056 ). Springer, Berlin Heidelberg 2015, ISBN 978-3-662-46799-2 , p. 368-397 , doi : 10.1007 / 978-3-662-46800-5_15 .
3. ↑ SPHINCS: Introduction. Retrieved January 25, 2019 . 

Web links

• Efficient Use of Merkle Trees - Declaration by RSA Security for the original purpose of Merkle trees: the handling of many Lamport one-time signatures.