Welcome Ninjas. This blog will discuss the Merkle Signature Scheme. Before proceeding with the topic, what does a signature specify in real life? It determines that whoever's signed it is responsible for it and agrees with the terms and conditions.

What if we want the same scheme for digital documents and messages? Here, we introduce the signature schemes. Let us get started!

Signature Schemes

A digital signature scheme protects a digital document from unauthorized access. A Digital Signature Scheme has two components

a private signing algorithm that permits a user to sign a message securely

a public verification algorithm that allows anyone to verify that the signature is authentic and verified.

A signature scheme forms a tuple (P, A, K, S, V) where:

P defines a finite set of possible messages

A represents a finite set of possible signatures

K represents a finite set of possible keys

For all k, there is a signature algorithm sigk in S and a verification algorithm verk in V such that:

sigk : P â†’ A

verk : P Ã— A â†’ {true,false}

verk(x,y) = true iff y=sigk (x)

A pair (x,y) that belongs to P Ã— A is called a signed message

We have various signing algorithms that bind a signature to a message or document so that the same signature can not be used to sign another document or modify the original message.

Merkle Signature Scheme

Developed by Ralph Merkle, Merkle Signature Scheme belongs to the category of Hash-based cryptography. It is based on Merkle Trees and one-time signatures.

Merkle Trees

A Merkle Tree is a binary tree in which every leaf node is assigned with the cryptographic hash of a data block. The other nodes (except the leaf nodes) are assigned the cryptographic hash of the labels of their respective child nodes. Reaching the leaf node from the parent node becomes such a task as it requires the computation of several hashes (proportional to the log(number of leaf nodes)). The tree's root is used as a fingerprint for the entire data.

For hashing in Merkle/Hash Trees, we use the hash function - SHA-2. Unsecured checksums like CRCs can be used to protect the hash tree against damage.

One-time Signature Scheme(Lamport)

In Lamport One time Signature Scheme, we can securely sign one message. Like other digital signature schemes, it also involved using the hash function. It takes place in 3 steps:

Key Generation

Signature Generation

Signature Verification

The construction of the Merkle tree considers Lamportâ€™s 1-time signature (KeyGen, SignGen, Verify) as well as the hash functions {h: {0,1}4n2 â†’ {0,1}n} used in the construction of our signature scheme which signs nlog(n) messages of length n.

Letâ€™s say we have a complete tree of height, say, k = log2(n), which will have a secret key and a public key at each node. Only the public key PK of the root of this tree will be published.

If we need to sign the i-th message in the tree, we sign it on the i-th leaf using Lamportâ€™s one-time signature. Then, we include the public keys of the nodes we cross from the leaf to the root node and their siblings. To make the path authentic, we need to have each parent sign the public keys of its children. We do this by concatenating the public keys of the two children and then adding a hash to it. Then we sign the result. All of this information is to be included in the signature.

Frequently Asked Questions

What does a cryptographic hash function do?

It is an algorithm that takes arbitrary length inputs and produces fixed-length outputs.

What is Lamport One time signature scheme?

It is used as a method to create digital signatures. It involves hash-based cryptography.

What is asymmetric encryption/cryptography?

In asymmetric cryptography, the data is encrypted and decrypted using two separate keys-public and private keys.

Conclusion

We hope the blog helped you understand the concept of the Merkle Signature Scheme.

If you found this blog interesting and insightful, refer to similar blogs: