Signature Merkle

Merkle's signature is a post-quantum and reusable digital signature algorithm based on the use of the Merkle tree and any one-time digital signature. ^[one]

Content

1 History
2 Description of the algorithm
- 2.1 Preparation
- 2.2 Key Generation
- 2.3 Signature Generation
- 2.4 Signature Verification
3 Benefits
- 3.1 Post-quantum
- 3.2 Reusability
4 disadvantages
- 4.1 Tree traversal problem
5 Cryptanalysis
6 notes
7 Literature

History

The signature was first published by Ralph Merkle in 1979 in his article “Secrecy, authentication, and public key systems” ^[2] , as a reusable digital signature using Lamport's one-time signature . ^[3]

Algorithm Description

Preparation

Merkle's signature is based on an already existing one-time digital signature, the cryptographic strength of which should be based on a cryptographic hash function . Examples of such signatures are the Winternitz One-time Signature Scheme or Lamport's signature . ^[4] A one-time digital signature should consist of three main operations: ^[5]

Secret key generation $X$ ${\ displaystyle X}$ $X$ and public key $Y$ ${\ displaystyle Y}$ $Y$ .
Signature Generation $b$ ${\ displaystyle b}$ $b$ from message $d$ ${\ displaystyle d}$ $d$ using a secret key $X$ ${\ displaystyle X}$ $X$ .
Signature Verification $b$ ${\ displaystyle b}$ $b$ using public key $Y$ ${\ displaystyle Y}$ $Y$ .

It is also necessary to determine the cryptographic hash function $H:\{0,1\}^{*}\rightarrow \{0,1\}^{s}$ ${\ displaystyle H: \ {0,1 \} ^ {*} \ rightarrow \ {0,1 \} ^ {s}}$ $H:\{0,1\}^{*}\rightarrow \{0,1\}^{s}$ , which will later be used to calculate the public key. ^[four]

Merkle Tree for Eight Keys

Key Generation

Key arrays are generated $X$ ${\ displaystyle X}$ $X$ and $Y$ ${\ displaystyle Y}$ $Y$ lengths $N=2^{n}$ ${\ displaystyle N = 2 ^ {n}}$ $N=2^{n}$ . The length is chosen equal to the power of two, as it is necessary to build a Merkle tree. Every couple $(X_{i},Y_{i})$ ${\ displaystyle (X_ {i}, Y_ {i})}$ $(X_{i},Y_{i})$ used as a private-public key pair for a basic one-time signature. Array $X$ ${\ displaystyle X}$ $X$ - is the private key of Merkle's signature; to generate the public key, the Merkle tree is built:

For everybody $Y_{i}$ ${\ displaystyle Y_ {i}}$ $Y_{i}$ calculate the hash value $H(Y_{i})$ ${\ displaystyle H (Y_ {i})}$ $H(Y_{i})$ - this will be the zero layer of the tree, that is, its leaves. Denote this layer $a_{0}$ ${\ displaystyle a_ {0}}$ $a_{0}$ . Total $a_{0}$ ${\ displaystyle a_ {0}}$ $a_{0}$ contains $l_{0}=2^{n}$ ${\ displaystyle l_ {0} = 2 ^ {n}}$ $l_{0}=2^{n}$ elements. Then we calculate the following $a_{1}$ ${\ displaystyle a_ {1}}$ size layer $l_{1}=2^{n-1}$ ${\ displaystyle l_ {1} = 2 ^ {n-1}}$ : everyone $j$ ${\ displaystyle j}$ layer element $a_{1}$ ${\ displaystyle a_ {1}}$ calculated through two elements from the previous layer $a_{1,j}=H(a_{0,j*2}||a_{0,j*2+1})$ ${\ displaystyle a_ {1, j} = H (a_ {0, j * 2} || a_ {0, j * 2 + 1})}$ where $||$ ${\ displaystyle ||}$ - concatenation operation. So every next $i$ ${\ displaystyle i}$ layer, has a length $l_{i}=2^{n-i}$ ${\ displaystyle l_ {i} = 2 ^ {ni}}$ and calculated through $i-1$ ${\ displaystyle i-1}$ th layer. In the end, we will come to the last layer of the tree $a_{n}$ ${\ displaystyle a_ {n}}$ having a length $l_{n}=1$ ${\ displaystyle l_ {n} = 1}$ and being the root of the tree.

For the public key, the root of the constructed Merkle tree is taken: $pub\_key=a_{n}$ ${\ displaystyle pub \ _key = a_ {n}}$ . ^[6]

Merkle tree for eight keys with authentication path

Signature Generation

To generate a signature from arrays $X$ ${\ displaystyle X}$ and $Y$ ${\ displaystyle Y}$ is selected $i$ ${\ displaystyle i}$ key pair $(X_{i},Y_{i})$ ${\ displaystyle (X_ {i}, Y_ {i})}$ .For message $d$ ${\ displaystyle d}$ a one-time digital signature is calculated $b_{i}$ ${\ displaystyle b_ {i}}$ using private key $X_{i}$ ${\ displaystyle X_ {i}}$ . Next, consider the path from the root $a_{0,n}$ ${\ displaystyle a_ {0, n}}$ Merkle tree to leaf $a_{0,i}$ ${\ displaystyle a_ {0, i}}$ corresponding to the key $Y_{i}$ ${\ displaystyle Y_ {i}}$ . Denote the vertices through which this path passes, as an array $A$ ${\ displaystyle A}$ lengths $n+1$ ${\ displaystyle n + 1}$ where $A_{n}$ ${\ displaystyle A_ {n}}$ Is the root of the tree, and $A_{0}$ ${\ displaystyle A_ {0}}$ - this is $a_{0,i}$ ${\ displaystyle a_ {0, i}}$ . Value of each vertex $A_{j}$ ${\ displaystyle A_ {j}}$ , Besides $A_{0}=H(Y_{i})$ ${\ displaystyle A_ {0} = H (Y_ {i})}$ is calculated as $H(A_{j-1}||auth_{j-1})$ ${\ displaystyle H (A_ {j-1} || auth_ {j-1})}$ where $auth_{j-1}$ ${\ displaystyle auth_ {j-1}}$ and $A_{j-1}$ ${\ displaystyle A_ {j-1}}$ are immediate descendants $A_{j}$ ${\ displaystyle A_ {j}}$ . Thus, in order to calculate the path from the root of the tree, it is enough to know $Y_{i}$ ${\ displaystyle Y_ {i}}$ and an array of vertices $auth_{1},auth_{2},...,auth_{n}$ ${\ displaystyle auth_ {1}, auth_ {2}, ..., auth_ {n}}$ , which we will call the authentication path. So in the message signature $d$ ${\ displaystyle d}$ included: verification key $Y_{i}$ ${\ displaystyle Y_ {i}}$ one time signature $b_{i}$ ${\ displaystyle b_ {i}}$ and an authentication path to calculate the path to the root of the tree. ^[7]

Signature Verification

First, the recipient verifies the one-time signature $b_{i}$ ${\ displaystyle b_ {i}}$ for compliance with the message $d$ ${\ displaystyle d}$ . If the test was successful, then begins to build the path from $H(Y_{i})$ ${\ displaystyle H (Y_ {i})}$ to the root of the tree. First calculated $A_{0}=H(Y_{i})$ ${\ displaystyle A_ {0} = H (Y_ {i})}$ , then $A_{1}=H(A_{0}||auth_{0})$ ${\ displaystyle A_ {1} = H (A_ {0} || auth_ {0})}$ and so on. If $A_{n}=pub\_key$ ${\ displaystyle A_ {n} = pub \ _key}$ , then the verification of the signature was successful. ^[8]

Benefits

Post-Quantum

Commonly used digital signature algorithms such as RSA and DSA use the complexity of factoring numbers and the complexity of computing the discrete logarithm . However, using the Shore algorithm and a quantum computer , these signatures can be cracked in polynomial time. In contrast, Merkle's signature is post-quantum, since its cryptographic strength is based on the strength of the cryptographic hash function and the strength of a one-time digital signature. ^[one]

Reusability

One of the main problems of digital signatures based on cryptographic hash functions is that they are usually used in the context of one-time digital signatures, that is, signatures in which one key pair is used to sign only one message. However, there are ways to expand such signatures to reusable ones. One of such methods is just building a Merkle tree, which is used to authenticate various one-time signatures. ^[9]

Weaknesses

Tree traversal problem

This problem is associated with finding an effective algorithm for calculating authentication data. The trivial decision to save all the data in memory requires too much memory. On the other hand, the approach of computing the authentication path in the area where it is needed will be too costly for some tree nodes. ^[10] If the lengths of the X and Y arrays are greater than 2 ^ 25, using Merkle's signature becomes impractical. ^[8]

Cryptanalysis

It is proved that the Merkle digital signature algorithm is cryptographic against an adaptive attack with a choice of messages if it uses a hash function that is resistant to collisions of the second kind. ^[11] ^[12] However, in order to crack Merkle's signature, a cryptanalyst needs to either restore the inverse image of the hash function or calculate a collision of the first kind. This means that, from a practical point of view, the cryptographic strength of Merkle's signature is based on the irreversibility of the hash function used and on its resistance to collisions of the first kind. ^[12]

Notes

↑ ¹ ² CMSS, 2006 , p. 349-350.
↑ Merkle, 1979 .
↑ Security, 2005 , p. one.
↑ ¹ ² CMSS, 2006 , p. 352.
↑ CMSS, 2006 , p. 351.
↑ Security, 2005 , p. 3.
↑ CMSS, 2006 , p. 352-353.
↑ ¹ ² CMSS, 2006 , p. 353.
↑ dods2005hash, 2005 , p. 96.
↑ szydlo2004merkle, 2004 , p. 541.
↑ Security, 2005 , p. four.
↑ ¹ ² rohde2008fast, 2008 , p. 109.

Literature

Merkle, Ralph Charles. Secrecy, authentication, and public key systems : Technical Report No. 1979-1. - Citeseer, 1979. - DOI : 10.1.1.637.3952 .

Garcıa, LC Coronado. On the security and the efficiency of the Merkle signature scheme : Technical Report 2005/192. - Cryptology ePrint Archive, 2005.

Buchmann, Johannes. CMSS – an improved Merkle signature scheme // International Conference on Cryptology in India. - Springer Berlin Heidelberg, 2006 .-- S. 349-363 . - DOI : 10.1007 / 11941378_25 . (inaccessible link)

Dods, Chris and Smart, Nigel P and Stam, Martijn. Hash based digital signature schemes // IMA International Conference on Cryptography and Coding. - Springer Berlin Heidelberg, 2005. - S. 96-115 . - DOI : 10.1007 / 11586821_8 .

Szydlo, Michael. Merkle tree traversal in log space and time // International Conference on the Theory and Applications of Cryptographic Techniques. - Springer Berlin Heidelberg, 2004 .-- S. 541-554 . - DOI : 10.1007 / 978-3-540-24676-3_32 .

Rohde, Sebastian and Eisenbarth, Thomas and Dahmen, Erik and Buchmann, Johannes and Paar, Christof. Fast hash-based signatures on constrained devices // International Conference on Smart Card Research and Advanced Applications. - Springer Berlin Heidelberg, 2008 .-- S. 104-117 . - DOI : 10.1007 / 978-3-540-85893-5_8 .

[_fa50728bc9330582-1] ¹ ² CMSS, 2006 , p. 349-350.

[_f6a4a19ad2153239-2] Merkle, 1979 .

[_6420f100fc64d9fd-3] Security, 2005 , p. one.

[_3d1bd4b16c2240d7-4] ¹ ² CMSS, 2006 , p. 352.

[_23f8e3b15e230e16-5] CMSS, 2006 , p. 351.

[_72f4ff0104160437-6] Security, 2005 , p. 3.

[_2536a0970174d56f-7] CMSS, 2006 , p. 352-353.

[_397ec1b16b8525e0-8] ¹ ² CMSS, 2006 , p. 353.

[_a0bc76390156cad4-9] s2005hash, 2005 , p. 96.

[_2a5c8a80bc2120e4-10] szydlo2004merkle, 2004 , p. 541.

[_7e2bfa010b2a159a-11] Security, 2005 , p. four.

[_d1c805b48e65e4a9-12] ¹ ² rohde2008fast, 2008 , p. 109.