*Scribed by Anand Bhaskar*

** Summary **

Today we show how to construct an inefficient (but efficiently verifiable) signature scheme starting from a one-time signature scheme.

Next time we shall see how to make it efficient using a pseudorandom function.

** From One-Time Signatures to Fully Secure Signatures **

Assume we have a -secure one-time signature scheme such that if is the length of messages that can be signed by , then the length of public keys generated by is at most .

(Lamport’s signatures do not satisfy the second property, but in Lecture 20 we described how to use a collision-resistant hash function to turn Lamport’s scheme into a scheme that can sign longer messages. We can arrange the parameters of the construction so that the hash-and-sign scheme can sign messages at least twice as long as the public key.)

We describe a scheme in which the key generation and signing have exponential complexity; later we will see how to reduce their complexity.

- Key Generation: run times, once for every string of length at most , and produce a public key / secret key pair .
It is convenient to think of the strings of length at most as being arranged in a binary tree, with being the parent of and , and the empty string being the root.

- Public Key: (where is the empty string)
- Secret Key: the set of all pairs for all of length .

- Sign: given a message of length , denote by the string made of the first bits of . Then the signature of is composed of parts:
- : the signature of using secret key , along with the value of the matching public key
- the signature of the public keys corresponding to and its sibling, signed using the secret key corresponding to the parent of , along with the public keys

- Verify. The verification algorithm receives a public key , a message , and a signature made of pieces: the first piece is of the form , the following pieces are of the form , for , and the last piece is of the form .
The verification algorithm:

- checks is valid;
- For , if it checks that , and if it checks that ;
- For , it checks that is valid. (For the case , we take .)

We visualize the -bit messages as labels for the leaf nodes of an level complete binary tree. Each node of the tree represents a public-secret key pair . The above scheme signs a message by first using the one-time signature function to sign using the secret key at its corresponding leaf node, and releasing the public key for that node as part of the signature. Now the sender needs to convince the receiver that public key was really generated by the sender and not a forger. So the sender signs the message consisting of and its sibling, namely

using the secret key of their parent node , and releases these two public keys and the public key as part of the message. The sender now has to convince the receiver that was generated by the sender, and it can apply the previous procedure again to do this. This signing procedure moves up the tree from signing the message at the leaf node to signing messages of two public keys at each level of the tree until it gets to the root node. The root public key doesn’t have to be signed since this is the public key that is released by the sender at the very beginning for all future communication.

Each public-secret key pair node in this tree is used to sign only one message – either the message corresponding to the leaf node if the key is at a leaf node, or the message that is the concatenation of the public keys at its two children. Note that the public key length is and so there are only distinct public keys in this tree which has nodes. There will certainly be many copies (on average ) of each public key at different nodes of the tree. We might be concerned that an adversary might then see many signatures for the same public key and have a much higher chance of breaking the one-time signature scheme for some public key. But if this attack was feasible, then the adversary might as well have generated public-secret key pairs by calling and checking if one of these matched some public key seen in the signature of some earlier message – thus, in this scheme, the adversary doesn’t get any extra power from seeing multiple signatures using the same key pair.

The theorem below shows that if it is hard for an adversary to forge signatures for the one-time signature scheme , then it will be also be hard to forge signatures under this tree-scheme.

Theorem 1Suppose that the scheme described in this section is not existentially unforgeable against a chosen message attack.

Then is not a -secure one time signature scheme, where is the maximum of the running time of and .

*Proof:* If the tree-scheme is not existentially unforgeable against a chosen message attack, then there exists an algorithm with complexity such that

makes queries to the signing oracle before outputting a fresh message and its forged signature. Hence, can only see public keys (and signatures using them) generated by the key generation algorithm . Using as a subroutine, we will construct an algorithm which given as input a public key of the signature scheme and one-time access to the signature function will forge a signature for a fresh message with probability .

picks a random integer in and using the key generation algorithm , generates key pairs

For notational convenience, set .

now simulates on input . Whenever makes a call to with a given message, performs the signing algorithm of the tree-scheme by using the public-secret key pairs it randomly generated at the beginning. will keep track of which nodes of the tree were already assigned key pairs from it’s cache of key pairs. Since at worst key pairs are needed for performing the signatures requested by , can satisfy all these signature queries using its generated key pairs. If needs to sign using , it will use its one-time access to to perform this action. won’t have to call twice with different messages since a public key is never used to sign more than one message in the tree-scheme, unless coincidentally is present as another in the list of key-pairs generated, in which case would have the secret key corresponding to and can completely break . The view of being run in the simulation by is exactly the same as if had been run on a random public key as input. Hence, the probability produces a forgery is .

If produces a fresh message and its valid signature

then let be the largest integer such that was seen by as part of the signature of some message at position in the virtual signature tree. Hence, must be one of the keys generated by . Such a value of must exist because certainly is a candidate for (since the public key was given as input to ).

Based on the value of , there are two cases:

- . Hence, for some , and if , then will output the message-signature pair as a forgery.

because this was part of the valid tree-scheme signature of message output by . By the definition of , has never seen the signature of before. Since the position was chosen randomly, the event has probability . - . Here, all the intermediate public keys in the forged signature of match those seen by (and hence match the keys generated by ), but the signature of at the last level of the tree itself has not been seen. Hence, for some and because is a valid forge produced by . If , then outputs the forged message-signature pair . Again, since the position was chosen randomly, the event has probability .

Conditioned on algorithm outputting a forge to the tree scheme, in both cases algorithm produces a forge to the original scheme with probability . Hence, the probability that produces a forge to is . The running time of the simulation is dominated by having to generate key pairs and performing signatures using for each of the signing queries made by , and is .