Summary
In the last lecture we described a very complex signature scheme based on one-time signatures and pseudorandom functions. Unfortunately there is no known simple and efficient signature scheme which is existentially unforgeable under a chosen message attack under general assumptions.
Today we shall see a very simple scheme based on RSA which is secure in the random oracle model. In this model, all parties have oracle access to a random function . In implementations, this random function is replaced by a cryptographic hash function. Unfortunately, the proof of security we shall see today breaks down when the random oracle is replaced by hash function, but at least the security in the random oracle model gives some heuristic confidence in the design soundness of the construction.
1. The Hash-and-Sign Scheme
Our starting point is the “textbook RSA” signature scheme, in which a message is signed as
and an alleged signature
for a message
is verified by checking that
.
We discussed various ways in which this scheme is insecure, including the fact that
- It is easy to generate random message/ signature pairs
by first picking a random
and then setting
;
- If
is the signature of message
and
is the signature of
, then
is the signature of
.
Suppose now that all parties have access to a good cryptographic hash function, which we will model as a completely random function , mapping every possible message
to a random integer
, and define a signature scheme
as follows:
- Key generation: as in RSA
- Signature: the signature of a message
with secret key
is
- Verification: given an alleged signature
, a message
, and a public key
, check that
.
That is, we use the textbook RSA method to sign .
Now it is not clear any more how to employ the previously mentioned attacks. If we first select a random , for example, then to find a message of which
is a signature we need to compute
and then find a message
such that
. This, however, requires exponential time if
is a random functions. Similarly, if we have two messages
and know their signatures
, the number
is a signature for any document
such that
. Finding such an
is, however, again very hard.
2. Analysis
We provide a formal analysis of the signature scheme defined in the previous section, in the random oracle model.
Theorem 1 Suppose that
, as defined in the previous section, is not
existentially unforgeable under a chosen message attack in the random oracle model.
Then RSA, with the key size used in the construction, is not a
-secure family of trapdoor permutations, where
is the time taken by RSA computation with the selected key size.