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
.
- Public Key:
- 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
.)
- checks
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
.