Digital Signature Compilers(2/3)-CMA security from KMA security

Let be a signature scheme in which the public keys have length and let be a signature scheme in which the message space includes all bit-strings of length Construct the signature scheme whose message space is exactly the message space of as follows:

Key generation: Simply runs to generate keys These are the public and secret keys, respectively.

Signature generation:

1. Run to generate keys .
2. 
   

3. 
   

4. Output the signature .

Signature verification:

Parse as Then output 1 if and only if both

and

Theorem:If is existentially unforgeable (resp., strongly unforgeable ) under a known-message attack and is unforgeable (resp., strongly unforgeable) under a one-time known-message attack,then is existentially unforgeable (resp., strongly unforgeable ) under an adaptive chosen-message attack.

:

Given a PPT adversary attacking the signature scheme denote by the experiment:

Let denote the th message submitted by to its signing oracle, and let denote the th signature received in return. Let be the event that and and define

The goal is to show that is negligible.

Let be  the event that for some

Claim. is negligible. Proof: Algorithm :

• Run a total of times to obtain keys
• Output Receive in return a public key along with the signatures (Note: each is a valid signature on with respect to )
• Run When requests a signature on the th message do:
1. Compute
2. Return the signature to .
• When outputs output

The view of in the above experiment is identical to its view in hence, the event occurs in the above execution of with probability exactly Since does not occur, we have since Forge occurs, it must be the case that is a valid signature on Hence, we conclude that outputs a forgery on a new message with probability The assumed security of under a known-message attack implies that this is negligible.

Claim. is negligible. Algorithm :

• Compute and choose a random index

• , answering its th signature query for a message as follows:

• Output and receive a public key and a signa
• Compute .
• Return the signature to .
• Run to generate keys .
• Compute and
• Return the signature to .
• Case
• Case

• When outputs if then output (else output nothing).

That is, chooses a random index and answers all signature queries of normally except for the th query; can do this since it knows the "master" secret key corresponding to For the th query for a signature, on the message , the adversary outputs to its own "oracle" and receives in return a randomly generated public key (generated using ) along with a signature on . It then computes the signature on on its own (using ) and returns to .

It is fairly easy to see that the view of in the above experiment is identical to its view in and therefore the probability that Forge Reuse occurs in the above experiment is exactly When Reuse occurs, there is at least one index for which since the distribution of is uniform given the view of we have that with probability at least Given that Forge occurs it must be the case that and and so outputs a valid forgery in this case. In summary, outputs a valid forgery with probability at least The claim follows.

The preceding two claims complete the proof.

Reference:

• S. Even, O. Goldreich, and S. Micali. On-line/off-line digital signatures. Journal of Cryptology, 9(1):35–67, 1996.