17 Digital signatures
---------------------

Digital signatures are the public key analogues of message
authentication schemes (MAC). They allow a *signer* to authenticate a
message with their *private key* by producing a tag that can
subsequently be verified by anyone who has the corresponding public
key. Just as with MACs the tags are specific to the message being
signed. Changing the message in any way should invalidate the tag,
thus the "signature". Also no-one who is not in the possession of the
private key corresponding to the public key used for verification
should be able to produce a valid signature.

Definition: a signature scheme is a triple Pi=(Gen,Sign,Vrfy) of ppt
algorithms where

1. Gen(n) produces a public/private key-pair (pk,sk) 

2. The signing algorithm Sign takes a secret key and a message m and
produces a signature sigma<-Sign_sk(m).

3. The (deterministic) verification algorithm Vrfy takes a public key,
a message m, and a signature sigma, and answers 1 or 0. If
sigma<-Sign_sk(m) then Vrfy_pk(m,sigma) must return 1.

If Sign_pk is defined only for messages of length l(n) for some
function l() then we speak of a *fixed length* signature scheme.

The signature scheme Pi=(Gen,Sign,Vrfy) is *secure* if the
success probability of the following experiment is negligible for any
ppt adversary A:

Experiment Sig-forge_{A,Pi}(n):

1. (pk,sk)<-Gen(n)

2. A gets n, pk, and oracle access to Sign_sk(). The adversary then
outputs (sigma,m). Let Q be the sequence of questions to the oracle
posed so far, i.e. messages for which a signature has been requested.

3. The outcome of the experiment is 1 iff Vrfy_pk(m,sigma)=1 and m is not in Q.

End of definition.

In KL our "secure" is called "existentially unforgeable under an adaptive
chosen-message attack" to differentiate from other, weaker notions of
security.


Insecure signature based on textbook RSA
- - - - - - - - - - - - - - - - - - - - -

A naive attempt at defining a signature scheme based on RSA goes as
follows:

Gen(n): (N,e,d)<-GenRSA(n);pk=(N,e);sk=(N,d)
   output (pk,sk)

Sign_{(N,d)}(m):
   output m^d mod N

Vrfy_{(N,e)}(m,sigma):
   output 1 iff sigma^e = m (mod N)

Clearly, verification of a valid signature succeeds but the scheme is
insecure for several reasons. First, if an adversary can choose an
arbitrary signature sigma first and then fabricate a corresponding
"message" as m=sigma^e mod N. Notice that Vrfy_{(N,e)}(m,sigma)
succeeds, so this adversary will win the experiment with certainty. 

Second, and perhaps more realistically, if the adversary would like to
get a signature on a previously fixed message m it could request
signatures sigma1 for random m1 and sigma2 for m2:=m/m1 (mod N). It is
then clear that sigma1*sigma2 mod N is a valid signature for the
original m.


Secure signatures with random oracles
- - - - - - - - - - - - - - - - - - -

It is possible, but rather inefficient, to construct secure signature
schemes based on the RSA assumption and a collision-resistant hash
function, see KL12.6. In practice, one uses signature schemes based on
cryptographic hash functions which can only be proved secure in the
random oracle model. We thus modify our definition of secure signature
scheme to the effect that both parties now have access to a function
H:{0,1}^n->{0,1}^n which is selected uniformly at random at the
beginning of the experiment.

In this situation we have the following signature scheme RSA-FDH
("full domain hash").

RSA-FDH:

Gen(n): (N,e,d)<-GenRSA(n);pk=(N,e);sk=(N,d)
   output (pk,sk)

Sign_{(N,d)}(m):
   output H(m)^d mod N

Vrfy_{(N,e)}(m,sigma):
   output 1 iff sigma^e = H(m) (mod N)

In practice, the random oracle H() will be replaced by a cryptographic
hash function such as SHA-2 and the scheme is just like the
abovedescribed insecure one with the exception that the message is
hashed prior to signing.

Let us see how this prevents the previous two attacks. Firstly, if the
attacker starts with arbitrary sigma then in order to fabricate a
corresponding message it would have to find m such that sigma^e=H(m)
(mod N) and thus for a given H()-value which it *can* compute, namely
sigma^e, find an inverse image, which is infeasible.

Similarly, in order to perpetrate the other attack it would have to
fabricate for given m two values x and y so that H(x)*H(y)=H(m).
While this is infeasible for truly random H() and not possible with
current knowledge for SHA-2 it is not prevented by mere
collision-resistance.

Theorem: If GenRSA() fulfills the RSA assumption then RSA-FDA is
secure in the random oracle model.

Proof: Let A be an attacker in the Sig-forge_{A,RSA-FDA}
experiment. We may fix a polynomial q(n) bounding the queries of A to
H() and also assume that A first queries H(m) for any message for
which it requests a signature or which it finally outputs. We also
assume that A makes exactly q(n) queries. All this is done in order to
save a few case distinctions in the argument.  We now build from A an
attacker A' against GenRSA() in the RSA-inv(n) experiment from Chapter
12 as follows.

Attacker A' against GenRSA:

Given N, e, y* = x^e mod N we (assuming the role of A') choose
j<-{1..q(n)} and forward the public key pk=(N,e) to A.

When A makes its i-th query m_i to H() we answer as follows:

If i=j we return y*.  If m_i has been asked previously, i.e., if
m_i=m_j for some j<i, then we answer consistently using a table to
store earlier answers.  Otherwise, we choose sigma_i <-Z_N^* uniformly
at random, answer y_i=sigma_i^e mod N and remember both y_i and
sigma_i in our table.

As a result, for all the H()-values that A has access to we know their
e-th root modulo N.

When A requests a signature on message m then, since H(m) has been
queried before, we have stored in our table sigma so that sigma^e=H(m)
and can thus return that very sigma which clearly is a valid
signature.

The only one message for which we do not have an e-th root is the j-th
one. Should the adversary A request a signature for the latter we
abort the experiment, i.e. return an arbitrary guess.

Finally, A will output a pair (m,sigma). If m=m_j and sigma^e=y* (mod
N) then we can output sigma (and we will win the RSA-inv experiment).

This concludes the description of the adversary A' against GenRSA().

We first note that even though we prepare the answers to A's
H()-queries using a table and case distinctions the resulting function
looks uniformly random from A's perspective. So, it, i.e. A, will work
just as in the standard Sign-forge experiment.

Now, A' wins the RSA-inv experiment if A produces a valid forgery
(m,sigma) and m = m_j.  If epsilon(n) is A's winning probability in
the Sig-forge experiment then this happens with probability
epsilon(n)*1/q(n). But by the RSA hardness assumption the latter
quantity is negligible and therefore, since q(n) is polynomial in n,
so is epsilon(n). QED 

We remark that a similar scheme based on discrete logarithms is known
as the Schnorr signature. 

Hash-and-sign
- - - - - - -

We note that if the hash function used here is arbitrary length then
the above scheme allows for the signing of messages of arbitrary
length. The security proof can be generalised to this, but becomes
somewhat awkward since arbitrary length random oracles have not been
properly defined.

Alternatively, one can turn any secure fixed length signature scheme
into an arbitrary length one by first hashing the message to be signed
with an arbitrary length collision-resistant hash function and then
signing the hash. The proof of security is analogous to the one for
the Hash-and-MAC paradigm given in Chapter 11. This is known as
"Hash-and-sign".