Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge

Full text

Pdf (1.43 MB)

Source

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

Dallas, Texas, United States

Pages: 399 - 408

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Oded Goldreich	Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
Amit Sahai	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
Salil Vadhan	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 36, 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/276698.276852 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.

	AH87	W'dliam Aiello and Johan H~tad. Perfect zero-knowledgelanguages can be recognized in two rounds. In Proceedings of the Twenty Eighth AnnuaI Symposium on Foundations of Cornpurer Science, pages 439-448,1987.
	BGG+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
	BMO90	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]
	Dam94	Ivan B. Damgård, Interactive hashing can simplify zero-knowledge protocol design without computational assumptions, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.100-109, January 1994, Santa Barbara, California, United States
	DGOW95	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
	DGW94	Ivan Damg~d, Oded Goldreich, and Avi Wigderson. Hashing functions can simplify zero-knowledge protocol design (too). Technical Report RS-94-39, BRiCS, November 1994. See Part 1 of{DGOW95}.
	DOY97	Giovanni Di Crescenzo , Tatsuaki Okamoto , Moti Yung, Keeping the SZK-Verifier Honest Unconditionally, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.31-45, August 17-21, 1997
	FGM+89	Martin Fiirer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos. On completeness and soundness in interactive proof systems. In Silvio Micali, editor, Advances in Computing Research, volume 5, pages 429-442. JAC Press, Inc., 1989.
	For89	Lance Formow. The complexity of perfect zero-knowIedge. In Silvio Mieali, editor, Advances in Computing Research, volume 5, pages 327-343. JAC Press, Inc., 1989.
	GG98	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 [doi>10.1145/276698.276704]
	GK93	Oded Goldreich and Eyal Kushilevitz. A perfect zeroknowledge proof system for a problem equivalent to the discrete logarithm. Journal of C07~tology, 6:97-116,1993.
	GK96	Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
	GM84	Shaft Goldwasser and Silvio Mieali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270-- 299, 1984.
	GMR89	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]
	GMW91	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]
	GO94	Oded Goldreich and Yah' Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cr37~tology, 7(1):I-32, Winter 1994.
	Gol95	Oded Goldreich. Foundations of Coptography (Fragments of a Book). Weizmann Institute of Science, February 1995. Available from http: //~w. eeoc. uni-trier, de/eccc/.
	GSV98	Oded Goldreich, Amit Sahai, and Salil Vadhan. Honestverifier statistical zero-knowledge equals general stc_tistieal zero-knowledge. Electronic Colloquium on Computational ComplexiU, 1998. htt:p://www.eccc.uni-t:rier/ eccc/.
	HILL	Johan H~tad, Russell impagUazzo, Leonid Levin, and Michael Luby. Construction of pseudorandom generator from any one-way function. To appear in SICOMP. Fxeliminary versions by Impagliazzo et. al. in 21st STOC (1939) and Hlstad in 22nd STOC (1990).
	IY87	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
	Nao91	Moni Naor. Bit commitment using pseudorandomne.~. Jottrnal of Co~ptology, 4(2):151-158,1991.
	Oka96	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]
	OVY93	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
	OW93	Rafail Ostrovsky and Avi Wigderson. One-way functions are, essential for non-trivial zero-knowledge. In Proceedings of the Second Israel Symposium on Theoo' of Computing and Sys. toms, 1993.
	SV97	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
	Yao82	Andrew C. Yao. Theory and application of trapdoor functions, in Proceedings of the 71venty Third Annual Symposlum on Foundations of Computer Science, pages 80-91, 1982.

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
	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
	Dorit Aharonov , Amnon Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Luis von Ahn , Andrew Bortz , Nicholas J. Hopper, k-anonymous message transmission, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA
	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
	Saurabh Sanghvi , Salil Vadhan, The round complexity of two-party random selection, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	John Watrous, Zero-knowledge against quantum attacks, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	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