Public-key cryptosystems provably secure against chosen ciphertext attacks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Public-key cryptosystems provably secure against chosen ciphertext attacks

Full text

Pdf (1.10 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 427 - 437

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

M. Naor	IBM Research, Almaden Research Center, 650 Harry Road, San-Jose CA
M. Yung	IBM Research, T . J . Watson Research Center, Yorktown Heights, NY 10598

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 29, Downloads (12 Months): 92, Citation Count: 36

Additional Information:

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/100216.100273 What is a DOI?

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.

	1	Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
	2	Mihir Bellare , Shafi Goldwasse, New Paradigms for Digital Signatures and Message Authentication Based on Non-Interative Zero Knowledge Proofs, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.194-211, August 20-24, 1989
	3	Mihir Bellare , Silvio Micali, How to sign given any trapdoor function, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.32-42, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62216]
	4	Manuel Blum , Paul Feldman , Silvio Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.103-112, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62222]
	5	[5] M. Blum, A. De Santis, S. Micali and, G. Persiano, Non-Interactive Zero-Knowledge, Manuscript.
	6	Manuel Blum , Shafi Goldwasser, An efficient probabilistic public key encryption scheme which hides all partial information, Proceedings of CRYPTO 84 on Advances in cryptology, p.289-302, August 1985, Santa Barbara, California, United States
	7	Alfredo De Santis , Silvio Micali , Giuseppe Persiano, Non-Interactive Zero-Knowledge Proof Systems, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.52-72, August 16-20, 1987
	8	[8] W. Diffie and M. Hellman, New Directions in Cryptography , IEEE Trans. on Information Theory 22(6), 1976, pp. 644-654.
	9	[9] U. Feige and A. Shamir, Witness Hiding and Witness Indistinguishability, STOC 1990.
	10	U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
	11	Zvi Galil , Stuart Haber , Moti Yung, Symmetric public-key encryption, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.128-137, June 1986, Santa Barbara, California, United States
	12	[12] O. Goldreich, A Uniform Complexity Encryption and Zero-knowledge, Technion CS-TR 570, June 1989.
	13	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	14	Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.268-282, July 16-20, 1990
	15	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	16	[16] S. Goldreich, S. Micali and A. Wigderson, Proofs that Yield Nothing But their Validity, and a Methodology of Cryptographic Protocol Design, Proceedings of the 27th Symposium on the Foundation of Computer Science, 1986, pp. 174-187.
	17	[17] S. Goldwasser and S. Micali, Probabilistic Encryption J. Com. Sys. Sci. 28 (1984), pp. 270-299.
	18	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	19	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]
	20	[20] S. Goldwasser, S. Micali and P. Tong, Why and How to Establish a Private Code on a Public Network, Proceedings of the 23rd Symposium on the Foundation of Computer Science, 1982, pp. 134-144.
	21	Leonid A. Levin, One-way functions and Pseudorandom generators, Combinatorica, v.7 n.4, p.357-363, Dec, 1987 [doi>10.1007/BF02579323]
	22	[22] R. Merkle and M. Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. on Information Theory, vol. IT-24, 5 (1978), pp. 525-530.
	23	[23] S. Micali, Personal Communication, February 1990.
	24	Silvio Micali , Charles Rackoff , Bob Sloan, The notion of security for probabilistic cryptosystems, SIAM Journal on Computing, v.17 n.2, p.412-426, April 1988 [doi>10.1137/0217025]
	25	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 [doi>10.1145/73007.73011]
	26	M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
	27	[27] C. Rackoff and D. Simon, Manuscript, 1990.
	28	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]
	29	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 [doi>10.1145/100216.100269]
	30	[30] M. Tompa and H. Woll, Random Self Reducibility and Zero-knowledge Interactive Proofs of Knowledge, Proceedings of the 28th Symposium on the Foundation of Computer Science, 1987.
	31	[31] A. C. Yao, Theory and Applications of Trapdoor functions , Proceedings of the 23th Symposium on the Foundation of Computer Science, 1982, pp. 80-91.
	32	Mordechai Yung, Cryptoprotocols: Subscription to a public key, the secret blocking and the multi-player mental poker game, Proceedings of CRYPTO 84 on Advances in cryptology, p.439-453, August 1985, Santa Barbara, California, United States
	33	S Zachos, Probabilistic quantifiers, adversaries, and complexity classes: an overview, Proc. of the conference on Structure in complexity theory, p.383-400, June 1986, Berkeley, California, United States

CITED BY 36

	Donald Beaver, Adaptive zero knowledge and computational equivocation (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.629-638, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Jonathan Katz , Moti Yung, Complete characterization of security notions for probabilistic private-key encryption, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.245-254, May 21-23, 2000, Portland, Oregon, United States
	Stuart Haber , Benny Pinkas, Securely combining public-key cryptosystems, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA
	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
	Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, 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
	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada
	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
	Alfredo De Santis , Yvo Desmedt , Yair Frankel , Moti Yung, How to share a function securely, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.522-533, May 23-25, 1994, Montreal, Quebec, Canada
	Benoît Libert , Jean-Jacques Quisquater, Efficient revocation and threshold pairing based cryptosystems, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.163-171, July 13-16, 2003, Boston, Massachusetts
	Brent R. Waters , Edward W. Felten , Amit Sahai, Receiver anonymity via incomparable public keys, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA
	Mihir Bellare , Ran Canetti , Hugo Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.419-428, May 24-26, 1998, Dallas, Texas, United States
	Giovanni Di Crescenzo , Yuval Ishai , Rafail Ostrovsky, Non-interactive and non-malleable commitment, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.141-150, May 24-26, 1998, Dallas, Texas, United States
	Ingrid Biehl , Sacher Paulus , Tsuyoshi Takagi, Efficient Undeniable Signature Schemes Based on Ideal Arithmetic in Quadratic Orders, Designs, Codes and Cryptography, v.31 n.2, p.99-123, February 2004
	Theodore Diament , Homin K. Lee , Angelos D. Keromytis , Moti Yung, The dual receiver cryptosystem and its applications, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA
	Juan Manuel Gonzalez Nieto , Colin Boyd , Ed Dawson, A Public Key Cryptosystem Based On A Subgroup Membership Problem, Designs, Codes and Cryptography, v.36 n.3, p.301-316, September 2005
	Mario Di Raimondo , Rosario Gennaro, New approaches for deniable authentication, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
	Xavier Boyen , Qixiang Mei , Brent Waters, Direct chosen ciphertext security from identity-based techniques, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
	Bogdan Warinschi, A computational analysis of the Needham-Schroeder-(Lowe) protocol, Journal of Computer Security, v.13 n.3, p.565-591, May 2005
	Xavier Boyen, A tapestry of identity-based encryption: practical frameworks compared, International Journal of Applied Cryptography, v.1 n.1, p.3-21, February 2008
	Oleg Izmerly , Tal Mor, Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment, Theoretical Computer Science, v.367 n.3, p.308-323, December, 2006
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	Jonathan Herzog, A computational interpretation of Dolev-Yao adversaries, Theoretical Computer Science, v.340 n.1, p.57-81, 13 June 2005
	Caroline Fontaine , Fabien Galand, A survey of homomorphic encryption for nonspecialists, European Journal of Information Systems, v.2007 n.1, p.1-15, January 2007
	Aggelos Kiayias , Moti Yung, Secure scalable group signature with dynamic joins and separable authorities, International Journal of Security and Networks, v.1 n.1/2, p.24-45, September 2006
	Chris Peikert , Brent Waters, Lossy trapdoor functions and their applications, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	David Galindo , Javier Herranz, On the security of public key cryptosystems with a double decryption mechanism, Information Processing Letters, v.108 n.5, p.279-283, November, 2008
	Ribao Wei , Dingfeng Ye, Delegate predicate encryption and its application to anonymous authentication, Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, March 10-12, 2009, Sydney, Australia
	Rui Zhang , Goichiro Hanaoka , Hideki Imai, A generic construction of useful client puzzles, Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, March 10-12, 2009, Sydney, Australia
	Hai-Bo Tian , Xi Sun , Yu-Min Wang, A new public-key encryption scheme, Journal of Computer Science and Technology, v.22 n.1, p.95-102, January 2007
	Isamu Teranishi , Wakaha Ogata, Relationship between Standard Model Plaintext Awareness and Message Hiding, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.244-261, January 2008
	Haifeng Qian , Yuan Zhou , Zhibin Li , Zecheng Wang , Bing Zhang, Efficient public key encryption with smallest ciphertext expansion from factoring, Designs, Codes and Cryptography, v.49 n.1-3, p.233-249, December 2008
	Yevgeniy Dodis , Yael Tauman Kalai , Shachar Lovett, On cryptography with auxiliary input, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Claude Castelluccia , Aldar C-F. Chan , Einar Mykletun , Gene Tsudik, Efficient and provably secure aggregation of encrypted data in wireless sensor networks, ACM Transactions on Sensor Networks (TOSN), v.5 n.3, p.1-36, May 2009
	Ming-Luen Wu, Nonce-aware encryption, Proceedings of the WSEAES 13th international conference on Computers, p.346-350, July 23-25, 2009, Rodos, Greece
	Xuhua Ding , Gene Tsudik , Shouhuai Xu, Leak-free mediated group signatures, Journal of Computer Security, v.17 n.4, p.489-514, December 2009