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:

    Sunshine of late afternoon—
    On the glass tray

    a glass pitcher, the tumbler
    turned down, by which

    a key is lying—And the
    immaculate white bed
    William Carlos Williams (1883–1963)

    ‘Society’ in America means all the honest, kindly-mannered, pleasant- voiced women, and all the good, brave, unassuming men, between the Atlantic and the Pacific. Each of these has a free pass in every city and village, ‘good for this generation only,’ and it depends on each to make use of this pass or not as it may happen to suit his or her fancy.
    Henry Brooks Adams (1838–1918)