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 matching public key
- 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 .)
Theorem 1 Suppose 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 running time of .