Merkle Signature Scheme - Key Generation

Key Generation

The Merkle Signature Scheme can only be used to sign a limited number of messages with one public key . The number of possible messages must be a power of two, so that we denote the possible number of messages as .

The first step of generating the public key is to generate the public keys and private keys of one-time signatures. For each public key, with, a hash value is computed. With these hash values a hash tree is built.

We call a node of the tree, where 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 and the root has level . We number all nodes of one level from the left to the right, so that is the leftmost node of level .

In the Merkle Tree the hash values are the leaves of a binary tree, so that . Each inner node of the tree is the hash value of the concatenation of its two children. So and .

In this way, a tree with leaves and nodes is built. The root of the tree is the public key of the Merkle Signature Scheme.

Read more about this topic:  Merkle Signature Scheme

Famous quotes containing the words key and/or generation:

    They have thrown away her electric toothbrush, someone else slips
    The key into the lock of her safety-deposit box
    At the Crocker-Anglo Bank; her seat at the cricket matches
    Is warmed by buttocks less delectable than hers.
    Randall Jarrell (1914–1965)

    My generation had Doris Day as a role model, then Gloria Steinem—then Princess Diana. We are the most confused generation.
    Erica Jong (b. 1942)