Scribed by Nick Jalbert
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.)
There are two major differences between signatures in a public key setting and MAC in a private key setting:
- Signatures are transferrable: Bob can forward
to another party and the other party can be confident that Alice actually sent the message, assuming a public key infrastructure is in place (or, specifically that the other party has Alice’s public key).
- Signature are non-repudiable: Related to the first difference, once Alice signs the message and sends it out, she can no longer deny that it was actually her who sent the message.
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.
- Generating random messages with valid signatures: In this attack, you pick a random string
and compute
and now
is a valid signature for
. This can be an effective attack if there are a large number of messages that are useful to forge.
- Combining signed messages to create the signature of their products: Suppose you have
and
with valid signatures
and
respectively. Note that
and
. We can now generate a valid signature for
:
- Creating signatures for arbitrary messages: Suppose the adversary wants to forge message
. If it is able to get a valid signature for a random message
and a specifically chosen message
then the adversary can use the second attack to calculate a valid signature for
(i.e.
and
.
Ideally, we would like the following notion of security, analogous to the one we achieved in the secret-key setting.
Definition 1 A signature scheme
is
existentially unforgeable under a chosen message attack if for every algorithm
of complexity at most
, 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.
It was initially thought no signature scheme could meet this definition. The so called “paradox” of signature schemes was that it seemed impossible to both have a scheme in which forgery is difficult (that is, equivalent to factoring) while simultaneously having this scheme be immune to chosen message attacks. Essentially the paradox is that the proof that a scheme is difficult to forge will generally use a black-box forging algorithm to then construct a factoring algorithm. However, if this scheme were subject to a chosen message attack, a new algorithm could be constructed which would simulate the constructed factoring algorithm and totally break the signature scheme. This new algorithm would be exactly the same as the one used in the forgery proof except every query to the black-box forging algorithm instead becomes one of the messages sent to the oracle. Goldwasser et al.’s paper “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks” gives further details and describes breaking the paradox.
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 most
, 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.
- KeyGen
: pick a secret key which consists of
-bit random strings
we now generate a public key by applying
to each
in our secret key:
- Sign
: we sign an
-bit message
with the signature
e.g. the message M:= 0110 gets the signature
- Verify
: we verify a message
‘s signature
by using public key
and checking
Theorem 3 Let
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.
Suppose this scheme does not provide a -one time signature. This implies that there must be an algorithm
with complexity
which makes 1 oracle query and
Intuitively, when we are given a string we want to use
to break the security of
and determines the pre-image of
.
We now describe the operation , the algorithm that breaks the security of
.
begins by generating a public key
(which requires
evaluations of
). Once
generates
, it sets a random position in it to the string
. Note the distribution of values in this modified
will look exactly to the same
because
is also an evaluation of
.
now runs
passing it
,
will query the oracle with a message to sign. With probability
this message will not require
to invert
. If this is the case, then with probability
generates a forged message
and signature
.
must differ from the oracle query by at least one bit, that is this forgery finds the inverse of at least one element of
not queried. This inverse will be
with probability
.
runs in time at most
if
is the running time of
and and inverts
with probability
. Thus if we take
to be
-secure, then this signature scheme must be
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.)
We use the hash function to hash the message into a string of the appropriate length and then sign the hash:
-
: generates a secret key and a public key
as
did above. Also picks a random seed
which becomes part of the public key.
-
:
-
:
Theorem 4 Suppose
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
.
We present a sketch of the proof of this theorem.
Suppose we had an algorithm that produced forged signatures with probability
after one oracle query. That is,
queries the oracle with message
and gets back
and then produces with probability
a message signature pair,
, such that
and
.
One of the two following cases must occur with probability :
- The message
has the same hash as
,
. This means
was able to find a collision in
. If
does this with probability
then it contradicts our security assumptions on
.
- If
, then
forged a signature for the original scheme
for a fresh message. If
can do this with probability
then it contradicts our security assumptions on
.
Because we reach a contradiction in both cases, must be a
secure one-time signature scheme.
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.