** Summary **

Today we begin to talk about *signature schemes*.

We describe various ways in which “textbook RSA” signatures are insecure, develop the notion of *existential unforgeability under chosen message attack*, analogous to the notion of security we gave for authentication, and discuss the difference between authentication in the private-key setting and signatures in the public-key setting.

As a first construction, we see Lamport’s *one-time signatures* based on one-way functions, and we develop a rather absurdly inefficient stateful scheme based on one-time signatures. The scheme will be interesting for its idea of “refreshing keys” which will be used next time to design a stateless, and reasonably efficient, scheme.

**1. Signature Schemes **

Signatures are the public-key equivalents of MACs. The set-up is that Alice wants to send a message to Bob, and convince Bob of the authenticity of the message. Alice generates a public-key/ secret-key pair , and makes the public key known to everybody (including Bob). She then uses an algorithm to compute a *signature* of the message; she sends the message along with the signature to Bob. Upon receiving , Bob runs a verification algorithm , which checks the validity of the signature. The security property that we have in mind, and that we shall formalize below, is that while a valid signature can be efficiently generated given the secret key (via the algorithm ), a valid signature cannot be efficiently generated without knowing the secret key. Hence, when Bob receives a message along with a signature such that outputs “valid,” then Bob can be confident that is a message that came from Alice. (Or, at least, from a party that knows Alice’s secret key.)

Syntactically, a signature scheme is a collection of three algorithms such that

- takes no input and generates a pair where is a public key and is a secret key;
- Given a secret key and a message , outputs a signature ;
- Given a public key , a message , and an alleged signature , outputs either “valid” or “invalid”, with the property that for every public key/ secret key pair , and every message ,

The notion of a signature scheme was described by Diffie and Hellman without a proposed implementation. The RSA paper suggested the following scheme:

- Key Generation: As in RSA, generate primes , generate such that , define , and let and .
- Sign: for a message , the signature of is
- Verify: for a message and an alleged signature , we check that .

Unfortunately this proposal has several security flaws. Ideally, we would like the following notion of security, analogous to the one we achieved in the secret-key setting.

Definition 1A signature scheme is existentially unforgeable under a chosen message attack if for every algorithm of complexity at mot , there is probability that , given a public key and a signing oracle, produces a valid signature of a message not previously sent to the signing oracle.

**2. One-Time Signatures and Key Refreshing **

We begin by describing a simple scheme which achieves a much weaker notion of security.

Definition 2 (One-Time Signature)A signature scheme is a -secure one-time signature scheme if for every algorithm of complexity at mot , there is probability that , given a public key and one-time access to a signing oracle, produces a valid signature of a message different from the one sent to the signing oracle.

We describe a scheme due to Leslie Lamport that is based on one-way function.

Theorem 3Let be a one way function computable in time . Then there is a one-time signature scheme that signs messages of length and that is secure.

A disadvantage of the scheme (besides the fact of being only a one-time signature scheme) is that the length of the signature and of the keys is much bigger than the length of the message: a message of length results in a signature of length , and the public key itself is of length .

Using a collision resistant hash function, however, we can convert a one-time signature scheme that works for short messages into a one-time signature scheme that works for longer messages. (Without significantly affecting key length, and without affecting the signature length at all.)

Theorem 4Suppose is a secure one-time signature scheme for messages of length , which has public key length and signature length . Suppose also that we have a secure family of collision-resistant hash functions . Suppose, finally, that all have running time at most .

Then there exists a secure one-time signature scheme with public key length , signature length and which can sign messages of length .

In particular, given a one-way function and a family of collision-resistant hash functions we can construct a one-time signature scheme in which the length of a signature plus the length of the public key is less than the length of messages that can be signed by the scheme.

If is such a one-time signature scheme, then the following is a stateful scheme that is existentially unforgeable under a chosen message attack.

Initially, the signing algorithm generates a public key/ secret key pair . When it needs to sign the first message , it creates a new key pair , and generates the signature . The signature of is the pair . When it, later, signs message , the signing algorithm generates a new key pair , and the signature . The signature of is the sequence

and so on. Of course it is rather absurd to have a signature scheme in which the signature of the 100th message contains in its entirety the *previously signed* 100 messages along with their signatures, but this scheme gives an example of the important paradigm of *key refreshing*, which will be more productively employed next time.