The (true) complexity of statistical zero knowledge

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The (true) complexity of statistical zero knowledge

Full text

Pdf (826 KB)

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: 494 - 502

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

M. Bellare	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA
S. Micali	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA
R. Ostrovsky	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): 2, Downloads (12 Months): 17, Citation Count: 9

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.100285 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	[1] Aiello W., and J. Hastad "Perfect Zero-Knowledge can be Recognized in Two Rounds" FOCS 87.
	2	Eric Bach, How to generate factored random numbers, SIAM Journal on Computing, v.17 n.2, p.179-193, April 1988 [doi>10.1137/0217012]
	3	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 [doi>10.1145/100216.100283]
	4	Michael Ben-Or , Oded Goldreich , Shafi Goldwasser , Johan Håstad , Joe Kilian , Silvio Micali , Phillip Rogaway, Everything Provable is Provable in Zero-Knowledge, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.37-56, August 21-25, 1988
	5	[5] Blum, M., "Coin Flipping over the Telephone," IEEE COMPCON 1982, pp. 133-137.
	6	[6] Brassard, G. and C. Crépeau, "Nontransitive Transfer of Confidence: A perfect Zero-knowledge Interactive protocol for SAT and Beyond," FOCS 86.
	7	Gilles Brassard , Claude Crépeau, Everything in NP can be Argued in Perfect Zero-Knowledge in a Bounded Number of Rounds, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.123-136, July 11-15, 1989
	8	U. Feige , A. Shamir, Witness indistinguishable and witness hiding protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.416-426, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100272]
	9	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 [doi>10.1145/28395.28418]
	10	[10] Goldreich, O. and A. Kahn, personal communication.
	11	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
	12	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]
	13	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]
	14	[14] Goldreich, O., Y. Mansour, and M. Sipser, "Interactive Proof Systems: Provers that never Fail and Random Selection," FOCS 87.
	15	[15] Goldreich, O., S. Micali, and A. Wigderson, "Proofs that Yield Nothing but their Validity", FOCS 86.
	16	[16] Goldreich, O., S. Micali and A. Wigderson, "A Completeness Theorem for Protocols with Honest Majority," STOC 87.
	17	[17] Oren Y., "On The Cunning Power of Cheating Verifiers: Some Observations About Zero Knowledge Proofs", FOCS 87.
	18	[18] Yao, A.C., "How to Generate and Exchange Secrets," FOCS 86.

CITED BY 9

	Salil Vadhan, On transformation of interactive proofs that preserve the prover's complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.200-207, May 21-23, 2000, Portland, Oregon, United States
	Ronald Cramer , Ivan Damgård, Linear zero-knowledge—a note on efficient zero-knowledge proofs and arguments, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.436-445, May 04-06, 1997, El Paso, Texas, United States
	Oded Goldreich , Rafail Ostrovsky , Erez Petrank, Computational complexity and knowledge complexity (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.534-543, May 23-25, 1994, Montreal, Quebec, Canada
	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
	Mihir Bellare , Shafi Goldwasser, Verifiable partial key escrow, Proceedings of the 4th ACM conference on Computer and communications security, p.78-91, April 01-04, 1997, Zurich, Switzerland
	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
	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
	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
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Zero-knowledge from secure multiparty computation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA