Shafi Goldwasser
Silvio Micali
Andy Yao
ABSTRACT
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
- 1.M. Blum, "Coin flipping by telephone", Proc. of IEEE, Spring Comp Con. 1982, 133-137.Google Scholar
- 2.L. Blum, M. Blum, M. Shub, "A Simple Secure Pseudo Random Number Generator", Crypto 1982.Google Scholar
- 3.R. DeMillo, N. Lynch, and M. Merritt, "Cryptographic protocols", Proc. 14th Ann. ACM Symp. on Th. of Comp., San Francisco, California, May 1982, 383-400. Google ScholarDigital Library
- 4.W. Diffie and M.E. Hellman, "New directions in cryptography", IEEE Trans. on Inform. Th. 22 (1976), 644-654.Google ScholarDigital Library
- 5.S. Goldwasser and S. Micali, "Probabilistic encryption and how to play mental poker keeping secret all partial information", Proc. 14th Ann. ACM Symp. on Theory of Computing, May 1982, San Francisco, California, 365-377. Google ScholarDigital Library
- 6.S. Goldwasser, S. Micali, and P. Tong, "How to establish a private code on a public network", Proc. 23rd Ann. IEEE Symp. on Found. of Comp. Sci., Oct. 1982, Chicago, Illinois.Google ScholarDigital Library
- 7.M. Rabin, "Digitalized signatures and public-key functions as intractable as factorization", in MIT/LCS/TR-212, MIT Technical Memo, 1979. Google ScholarDigital Library
- 8.M. Rabin, "Digitalized signatures", in Foundations of Secure Computations, edited by R. DeMillo, D. Dobkin, A. Jones, and R. Lipton, Academic Press, 1978, 155-168.Google Scholar
- 9.R. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public key cryptosystems", Comm. ACM 21 (1978), 120-126. Google ScholarDigital Library
- 10.A. Shamir, "On the generation of cryptographically strong pseudo-random sequences", ICALP 1981. Google ScholarDigital Library
- 11.A. Yao, "Theory and Applications of Trapdoor Functions", Proc. 23rd Ann. IEEE Symp. on Found. of Comp. Sci., Oct. 1982, Chicago, Illinois.Google Scholar
Index Terms
- Strong signature schemes
Recommendations
Identity-based strong designated verifier signature schemes: Attacks and new construction
A strong designated verifier signature scheme makes it possible for a signer to convince a designated verifier that she has signed a message in such a way that the designated verifier cannot transfer the signature to a third party, and no third party ...
A novel identity-based strong designated verifier signature scheme
Unlike ordinary digital signatures, a designated verifier signature scheme makes it possible for a signer to convince a designated verifier that she has signed a message in such a way that the designated verifier cannot transfer the signature to a third ...
Identity-based strong designated verifier signature revisited
Abstract: Designated verifier signature (DVS) allows the signer to persuade a verifier the validity of a statement but prevent the verifier from transferring the conviction. Strong designated verifier signature (SDVS) is a variant of DVS, which only ...
Comments