The complexity of perfect zero-knowledge

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of perfect zero-knowledge

Full text

Pdf (606 KB)

Source

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

New York, New York, United States

Pages: 204 - 209

Year of Publication: 1987

ISBN:0-89791-221-7

Author

L. Fortnow

MIT Math Dept., Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 42, Citation Count: 17

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

ABSTRACT

A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for any language that has a perfect zero-knowledge proof system, its complement has a short interactive protocol. This result implies that there are not any perfect zero-knowledge protocols for NP-complete languages unless the polynomial time hierarchy collapses. This paper demonstrates that knowledge complexity can be used to show that a language is easy to prove.

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]
	BH	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]
	BC	Brassard, G. and C. Cr6peau, "Non- Transitive Transfer of Confidence' A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond", Pvoc. z97th FOCS, 1986, pp. 188-195.
	CW	Carter, J.L. and M.N. Wegman, "Universal Classes of Hash Functions", JC$$18 2, 1979, pp.143-154.
	GMW	Goldreich, O., S. Micali and A. Wigderson, "Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design", Proc. 27th FOCS, 1986, pp. 174-187.
	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]
	GS	S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
	S	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]

CITED BY 17

	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
	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
	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
	Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States
	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
	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
	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
	Ning Chen , Jia-Wei Rong, Memorizable interactive proof and zero-knowledge proof systems, Journal of Computer Science and Technology, v.19 n.6, p.936-941, November 2004
	Gilles Brassard, How convincing is your protocol?, ACM SIGACT News, v.22 n.1, p.5-12, Winter 1991
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	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
	Dario Catalano , Ivan Visconti, Hybrid commitments and their applications to zero-knowledge proof systems, Theoretical Computer Science, v.374 n.1-3, p.229-260, April, 2007
	Mike Burmester , Yvo G. Desmedt , Fred Piper , Michael Walker, A General Zero-Knowledge Scheme, Designs, Codes and Cryptography, v.12 n.1, p.13-37, Sept. 1997
	Oded Goldreich, A taxonomy of proof systems (part 2), ACM SIGACT News, v.25 n.1, p.22-30, March 1994
	Oded Goldreich, A taxonomy of proof systems (part 1), ACM SIGACT News, v.24 n.4, p.2-13, Dec. 1993
	M. Bellare , S. Micali , R. Ostrovsky, Perfect zero-knowledge in constant rounds, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.482-493, May 13-17, 1990, Baltimore, Maryland, United States
	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