Strong signature schemes
S Goldwasser, S Micali, A Yao - Proceedings of the fifteenth annual ACM …, 1983 - dl.acm.org
S Goldwasser, S Micali, A Yao
Proceedings of the fifteenth annual ACM symposium on Theory of computing, 1983•dl.acm.orgThe notion of digital signature based on trapdoor functions has been introduced by Diffie
and Hellman [3]. Rivest, Shamir and Adleman [8] gave the first number theoretic
implementation of a signature scheme based on a trapdoor function. If f is a trapdoor
function and ma message, f− 1 (m) is the signature of m. The signature can be verified by
computing f (f− 1 (m))= m. This approach presents the following problems even when f is
hard to invert: 1) there may be special message spaces (or subsets of them) that are easy to …
and Hellman [3]. Rivest, Shamir and Adleman [8] gave the first number theoretic
implementation of a signature scheme based on a trapdoor function. If f is a trapdoor
function and ma message, f− 1 (m) is the signature of m. The signature can be verified by
computing f (f− 1 (m))= m. This approach presents the following problems even when f is
hard to invert: 1) there may be special message spaces (or subsets of them) that are easy to …
The notion of digital signature based on trapdoor functions has been introduced by Diffie and Hellman[3]. Rivest, Shamir and Adleman[8] gave the first number theoretic implementation of a signature scheme based on a trapdoor function. If f is a trapdoor function and m a message, f−1(m) is the signature of m. The signature can be verified by computing f(f−1(m)) = m. This approach presents the following problems even when f is hard to invert:
1) there may be special message spaces (or subsets of them) that are easy to sign without knowing the trapdoor information
2) it is possible to forge the signature of random numbers; this violates the requirements of many protocols
3) given a polynomial number of signed messages, it may be possible to sign a new one without knowing the trapdoor information.
We solve the above problems by exhibiting two signature schemes for which any strategy of an adversary, who has seen all previously signed messages, that has a moderate success in forging even a single additional signature, is transformable to a fast algorithm for factoring or inverting the RSA function. This provably holds for all message spaces with all possible Probability distributions. Thus, in particular, given the signature of m, forging the signature of m+1 or 2m or 2sm is as hard as factoring. The two signature schemes