Digital Signature Compilers(1/3)-CMA security from RMA security
We all know that Fujisaki-Okamoto (FO) transformation can turn an IND-CPA secure encryption scheme into an IND-CCA secure one. So in the field of digital signatures, is there a similar general compiler that transforms weak security definition into strong security definition? We list three of them in this series.
There is no advanced mathematics needed, or not even any computational complexity assumptions involved.
The other two part of this series will be :
- Digital Signature Compilers(2 of 3) - CMA security from KMA security
- Digital Signature Compilers(3 of 3) - From Unforgeability to Strong Unforgeability
Let be a signature scheme for message of length . Construct the signature scheme for messages of length as follows:
Key generation: Run two (independent) invocations of to obtain the keys ,. The public key is and the secret key is
Signature generation:
Parse as Choose and Set Compute and Output the signature
Signature verification: Parse as and as Then, output 1 iff and both
and
Theorem:If is existentially unforgeable (resp., strongly unforgeable ) under a random-message attack, then is existentially unforgeable ( resp., strongly unforgeable) under an adaptive chosen-message attack.
:
Let be a PPT adversary attacking and denote by the experiment
Let be the event that
The goal is to show that is negligible.
In a given execution of let denote the th message submitted by to its signing oracle, and let denote the th signature received. Denote by the components of the signature output by .
Let denote the event that two signatures obtained by from its signing oracle use the same value for the nonce , that is, that for some
Let denote the set of "left" message/signature pairs. Let denote the event that and
Similarly, let be the set of "right" message/signature pairs, and let be the event that and
Assume occurs and does not occur. Since occurs, we know that and since does not occur, we know that for at most one value of . There are two cases to consider:
Case 1: is not equal to for any value of In this case, we clearly have for all and so, in particular, This means that occurs. (By a symmetric argument, occurs in this case as well.)
Case 2: for some (unique) If both and then we have and in contradiction to the fact that (since occurred). Thus, it must be the case that either (in which case occurs) or (in which case occurs )
We conclude that:
We show that each of the terms on the right-hand side is negligible, thus completing the proof of the theorem.
Claim. is negligible.
Proof. The claim follows easily from a "birthday problem" calculation. Specifically, We have nonces chosen uniformly from the set of size The probability that two of these values are equal is at most , which is negligible in .
Claim. is negligible.
Proof. To prove this claim, we reduce to the strong unforgeability of . Consider the following PPT adversary using as a subroutine and attacking in a random-message attack:
Algorithm A:The algorithm is given a public key , generated using along with signatures on the random messages
Set
Run to obtain keys .
Set and
When requests a signature on the th message do:
Let be the first bits of and let be the last bits of Compute Return the signature to . When outputs , then output
Observe first that provides a perfect simulation for that is, the view of when run by (and when is generated by ) is identically distributed to the view of in It is easy to see that the public key is identically distributed in both experiments. As for the answers to the signing queries of note that these, too, are distributed identically in both cases; here, we rely on the fact that the are chosen uniformly (and independently) at random.
To conclude the proof, we merely observe that outputs a strong forgery whenever occurs. So, the success probability of attacking with respect to a random-message attack is exactly equal to since is assumed to be strongly unforgeable under a random-message attack, this must be negligible.
An exactly analogous argument shows that is negligible.
Since each term on the right-hand side of Equation is negligible, we conclude that the success probability of in attacking under a chosen-message attack is negligible. This completes the proof of the theorem.
Reference:
R. Cramer and T. Pedersen. Efficient and provable security amplifications. Technical Report CS-R9529, CWI, 1995. R. Cramer. Modular Design of Secure yet Practical Cryptographic Protocols. PhD thesis, University of Amsterdam, 1996. D. Naccache, D. Pointcheval, and J. Stern. Twin signatures: An alternative to the hash-and-sign paradigm. In ACM CCS ’01: 8th ACM Conference on Computer and Communications Security, pages 20–27. ACM Press, 2001.