Private coins versus public coins in interactive proof systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Private coins versus public coins in interactive proof systems

Full text

Pdf (754 KB)

Source

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

Berkeley, California, United States

Pages: 59 - 68

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

S Goldwasser	Computer Science Department, MIT
M Sipser	Computer Science Department, University of California at Berkeley and Mathematics Department, MIT

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 60, Citation Count: 29

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

	B	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	Be	M. Ben-Or, personal communication.
	BH	R. Boppana, J. Hastad, I f co-NP Has Interactive Proof Systems with a Constant Number of Interactions, then the Polynomial Time Hierarchy Collapses, In prep.
	CKS	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	Co	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	CW	J.L. Carter, and M.N. Wegman, Universal classes of hash functions, JCSS 18, no. 2, 1979, 143-154.
	F	P. Feldman, The Prover in {P Need Not be More Powerful than PSPACE, personal communication.
	FS	L. Fortnow, M. Sipser, personal communication.
	H	J. Hastad, personal communication.
	GMR	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]
	GMW	O. Goldreich, S. Micali, A. Wigderson, Proofs that Yield Nothing but the Validity of their Assertion, In preparation.
	P	C. Papadimitriou, Games against nature, 24th FOCS 1983, 446-450,
	R	J. Reif, Games with imperfect information, JCSS 29, 274-301, 1984.
	Si	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	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]
	ZF	S. Zachos, M. Furer, Probabilistic quantifiers us. distrustful adversaries, to appear.

CITED BY 29

	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	U. Fiege , A. Fiat , A. Shamir, Zero knowledge proofs of identity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.210-217, January 1987, New York, New York, United States
	Oded Goldreich , Shafi Goldwasser, On the limits of non-approximability of lattice problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.1-9, May 24-26, 1998, Dallas, Texas, United States
	Oded Goldreich , Avi Wigderson, Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.574-584, May 23-25, 1994, Montreal, Quebec, Canada
	M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States
	Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States
	Cynthia Dwork , Larry Stockmeyer, Finite state verifiers I: the power of interaction, Journal of the ACM (JACM), v.39 n.4, p.800-828, Oct. 1992
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate PCPs, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.41-50, May 01-04, 1999, Atlanta, Georgia, United States
	Anne Condon, Space-bounded probabilistic game automata, Journal of the ACM (JACM), v.38 n.2, p.472-494, April 1991
	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992
	Joseph Halpern , Yjoram Moses , Mark Tuttle, A knowledge-based analysis of zero knowledge, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.132-147, May 02-04, 1988, Chicago, Illinois, United States
	Ker-I Ko, Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy, Journal of the ACM (JACM), v.37 n.2, p.415-438, April 1990
	Cynthia A. Brown , Larry Finkelstein , Paul Walton Purdom, Jr., Backtrack searching in the presence of symmetry, Nordic Journal of Computing, v.3 n.3, p.203-219, Fall 1996
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate probabilistically checkable proofs, Information and Computation, v.189 n.2, p.135-159, March 15, 2004
	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
	Avi Wigderson, The amazing power of pairwise independence (abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.645-647, May 23-25, 1994, Montreal, Quebec, Canada
	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
	Masao Hara , Seiichi Tani , Makoto Yamamoto, Unknotting is in AM ∩ co-AM, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Jin-Yi Cai , Hong Zhu, Progress in computational complexity theory, Journal of Computer Science and Technology, v.20 n.6, p.735-750, November 2005
	Cynthia Dwork , Larry Stockmeyer, Finite state verifiers II: zero knowledge, Journal of the ACM (JACM), v.39 n.4, p.829-858, Oct. 1992
	L. Fortnow, The complexity of perfect zero-knowledge, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.204-209, January 1987, New York, New York, United States
	Michael Luby , Avi Wigderson, Pairwise independence and derandomization, Foundations and Trends® in Theoretical Computer Science, v.1 n.4, p.237-301, August 2006
	Adi Akavia , Oded Goldreich , Shafi Goldwasser , Dana Moshkovitz, On basing one-way functions on NP-hardness, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Jin-Yi Cai, S2p⊆ZPPNP, Journal of Computer and System Sciences, v.73 n.1, p.25-35, February, 2007
	Ken-ichi Kawarabayashi , Bojan Mohar, Graph and map isomorphism and all polyhedral embeddings in linear time, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Lane A. Hemaspaandra, Lowness: a yardstick for NP-P, ACM SIGACT News, v.24 n.2, p.10-14, Spring 1993
	Oded Goldreich, A taxonomy of proof systems (part 2), ACM SIGACT News, v.25 n.1, p.22-30, March 1994
	Oded Goldreich, Probabilistic Proof Systems: A Primer, Foundations and Trends® in Theoretical Computer Science, v.3 n.1, p.1-91, January 2008
	Harumichi Nishimura , Tomoyuki Yamakami, An application of quantum finite automata to interactive proof systems, Journal of Computer and System Sciences, v.75 n.4, p.255-269, June, 2009