Computational complexity and knowledge complexity (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computational complexity and knowledge complexity (extended abstract)

Full text

Pdf (1.29 MB)

Source

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

Montreal, Quebec, Canada

Pages: 534 - 543

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Oded Goldreich	Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel
Rafail Ostrovsky	Computer Science Division, University of California at Berkeley and International Computer Science Institute, Berkeley, CA
Erez Petrank	Computer Science Department, Technion - Israel Institute of Technology, Haifa 32000, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 15, Citation Count: 2

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/195058.195406 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.

	AH-87	W. Aiello and J. H~stad. Perfect Zero-Knowledge can be Recognized in Two Rounds. Proceedings of the PSth Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1987).
	BMO-90	M. Bellare , S. Micali , R. Ostrovsky, The (true) complexity of statistical zero knowledge, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.494-502, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100285]
	BP-92	Mihir Bellare , Erez Petrank, Making zero-knowledge provers efficient, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.711-722, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129781]
	B+ 88	M. Ben-Or , O. Goldreich , S. Goldwasser , J. Håstad , J. Kilian , S. Micali , P. Rogaway, Everything provable is provable in zero-knowledge, Proceedings on Advances in cryptology, p.37-56, February 1990, Santa Barbara, California, United States
	BHZ-87	R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
	F-89	L. Fortnow. The Complexity of Perfect Zero-Knowledge. Advances #n Computing Research (ed. S. Micali) Vol. 18 (19s9).
	GMS-87	O. Goldreich, Y. Mansour and M. Sipser. Interactive Proof Systems: Provers that never Fail and Random Selection. Proceedings of the PSth Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1087).
	GMW-86	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
	GMW-87	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
	GP-91	Oded Goldreich , Erez Petrank, Quantifying knowledge complexity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.59-68, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185349]
	GMR-85	S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
	GMR-89	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]
	GS-89	S. Goldwasser, and M. Sipser, Private Coins vs. Public Coins in Interactive Proof Systems, Advances in Computzng Research (ed. S. Micali), 1989, Vol. 5, pp. 73-90.
	H-94	J. H#stad. Perfect Zero-Knowledge in .4A/{ n co-~4A#t. Unpublished 2-page manuscript explaining the underlying ideas behind {AH-87}. 1994.
	ILu-90	R. Impagliazzo and M. Luby, One-Way Functions are Essential for Complexity Based Cryptography, 30th FOCS, pp. 230-235, 1990.
	ILe-90	R. Impagliazzo and L.A. Levin, No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random, 31st FOCS, pp. 812-821, 1990.
	IY-87	Russell Impagliazzo , Moti Yung, Direct Minimum-Knowledge Computations, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.40-51, August 16-20, 1987
	JVV-86	M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
	LFKN-90	C. Land, L. Fortnow, H. Karloff and N. Nisan. Algebraic Methods for Interactive Proof Systems. Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1990).
	Ost-91	R. Ostrovsky. One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs. Proceedings of Structures In Complexity Theory 6th Annual Conference IEEE (1991).
	OW-93	R. Ostrovsky and A. Wigderson. One-Way Functions are Essential For Non-Trivial Zero-Knowledge, Proc. 2nd Israeh Symp. on Theory of Computing and Systems, 1993.
	OVY-91	R. Ostrovsky, R. Venkatesan and M. Yung. Fair Games Against an All-Powerful Adversary. A MS DIMACS Seines #n D#screte Mathematics and Theoretical Computer Science. Vol 13. (Jin-Yi Cai ed.) pp. 155-169.
	Sh-90	A. Shamir. IP--PSPACE. Proc. 22nd A CM Syrup. on Theory of Computing, pages 11-15, 1990.
	Si-83	Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
	St-83	Larry Stockmeyer, The complexity of approximate counting, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.118-126, December 1983 [doi>10.1145/800061.808740]

CITED BY 2

	Tatsuaki Okamoto, On relationships between statistical zero-knowledge proofs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.649-658, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	William Aiello , Mihir Bellare , Ramarathnam Venkatesan, Knowledge on the average—perfect, statistical and logarithmic, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.469-478, May 29-June 01, 1995, Las Vegas, Nevada, United States