How to sign given any trapdoor function

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How to sign given any trapdoor function

Full text

Pdf (962 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 32 - 42

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Mihir Bellare	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
Silvio Micali	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 30, Citation Count: 7

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/62212.62216 What is a DOI?

ABSTRACT

We present a digital signature scheme which combines high security with the property of being based on a very general assumption: the existence of trapdoor permutations. Previous signature schemes with comparable levels of security were based on assumptions of the computational hardness of particular algebraic problems such as factoring. Our contribution is to free this important cryptographic primitive from the fortunes of any specific algebraic problem by establishing a truly general signature scheme.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BBS	L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
	BM	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	DH	Diffie, W. and M. E. Hellman, "New Directions in Cryptography," tEEE Trans. Info. Theory IT-22 (November 1976), 644-654.
	GM	Goldwasser, S., and S. Micali, "Probabalistic Encryption," Journal of Computer and System Sciences 28 (April 1984), 270-299.
	GMR	Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
	GMY	Shafi Goldwasser , Silvio Micali , Andy Yao, Strong signature schemes, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.431-439, December 1983 [doi>10.1145/800061.808774]
	La	Lamport, L. "Constructing Digital Signatures from a One-V~ray Function," SRI Intl. CSL-98. (October 1979)
	Le	L A Levin, One-way functions and pseudorandom generators, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.363-365, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22185]
	M	Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
	RSA	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
	Y	Yao, A. C., "Theory and Applications of Trapdoor Functions," Proceedings of the 23rd Annual Symposium on the Foundations of Computer Science, IEEE (1982) 80-91.

CITED BY 7

	M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States
	Mihir Bellare , Silvio Micali, How to sign given any trapdoor permutation, Journal of the ACM (JACM), v.39 n.1, p.214-233, Jan. 1992
	Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States
	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States
	Moni Naor, Evaluation may be easier than generation (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.74-83, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States
	M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States