On transformation of interactive proofs that preserve the prover's complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On transformation of interactive proofs that preserve the prover's complexity

Full text

Pdf (863 KB)

Source

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

Portland, Oregon, United States

Pages: 200 - 207

Year of Publication: 2000

ISBN:1-58113-184-4

Author

Salil Vadhan

MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA

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): 19, 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/335305.335330 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	Vikraman Arvind , Johannes Köbler, On Resource-Bounded Measure and Pseudorandomness, Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, p.235-249, December 18-20, 1997
	2	László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
	3	Mihir Bellare , Shafi Goldwasser, The Complexity of Decision Versus Search, SIAM Journal on Computing, v.23 n.1, p.97-119, Feb. 1994 [doi>10.1137/S0097539792228289]
	4	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]
	5	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
	6	Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
	7	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]
	8	Peter Bro Miltersen , N. V. Vinodchandran, Derandomizing Arthur-Merlin Games Using Hitting Sets, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.71, October 17-18, 1999
	9	Ivan Damgård , Oded Goldreich , Tatsuaki Okamoto , Avi Wigderson, Honest Verifier vs Dishonest Verifier in Public Cain Zero-Knowledge Proofs, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.325-338, August 27-31, 1995
	10	Shimon Even , Alan L. Selman , Yacov Yacobi, The complexity of promise problems with applications to public-key cryptography, Information and Control, v.61 n.2, p.159-173, May 1984 [doi>10.1016/S0019-9958(84)80056-X]
	11	M. Fiirer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos. On completeness and soundness in interactive proof systems. In S. Micali, editor, Advances in Computing Research, volume 5, pages 429--442. JAC Press, Inc., 1989.
	12	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]
	13	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]
	14	Oded Goldreich , Amit Sahai , Salil Vadhan, Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.399-408, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276852]
	15	Oded Goldreich , Salil Vadhan, Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.54, May 04-06, 1999
	16	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]
	17	S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali, editor, Advances in Computing Research, volume 5, pages 73-90. JAC Press, Inc., 1989.
	18	Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
	19	R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
	20	Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
	21	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
	22	Joe Kilian, Achieving Zero-Knowledge Robustly, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.313-325, August 11-15, 1990
	23	Adam R. Klivans , Dieter van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.659-667, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301428]
	24	Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
	25	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
	26	Moni Naor , Omer Reingold, On the construction of pseudo-random permutations: Luby-Rackoff revisited (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.189-199, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258581]
	27	Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
	28	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 [doi>10.1145/237814.238016]
	29	Rafail Ostrovsky , Ramarathnam Venkatesan , Moti Yung, Interactive hashing simplifies zero-knowledge protocol design, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.267-273, January 1994, Lofthus, Norway
	30	Amit Sahai , Salil Vadhan, A Complete Promise Problem for Statistical Zero-Knowledge, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.448, October 19-22, 1997
	31	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	32	Salil Pravin Vadhan , Shafi Goldwasser, A study of statistical zero-knowledge proofs, 1999

CITED BY 2

	Amit Sahai , Salil Vadhan, A complete problem for statistical zero knowledge, Journal of the ACM (JACM), v.50 n.2, p.196-249, March 2003
	Minh-Huyen Nguyen , Salil Vadhan, Zero knowledge with efficient provers, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA