On relationships between statistical zero-knowledge proofs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On relationships between statistical zero-knowledge proofs

Full text

Pdf (986 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 649 - 658

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Tatsuaki Okamoto

NTT Laboratories, 1-2356 Take, Yokosuka-shi, 238-03 Japan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 19, Citation Count: 4

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/237814.238016 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	Aiello, W. and H~stad, J.: Perfect Zero- Knowledge Languages can be Recognized in Two Rounds. Proc. of FOCS (1987) 439-448
	Bab85	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]
	BCC88	Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
	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]
	B+ 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
	Dam93	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
	For89	Fortnow, L.: The Complexity of Perfect Zero- Knowledge. Advances in Computing Research (ed. S. Micali) Vol. 18 (1989)
	Gol89	Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
	GOP94	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 [doi>10.1145/195058.195406]
	GL89	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	GMS87	Goldreich, O., Mansour, Y. and Sipser, M.: Interactive Proof Systems: Provers that never Fail and Random Selection. Proc. FOCS (1987) 449-461
	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]
	GMW86	Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design. Proc. FOCS (1986) 174-187
	GS89	Goldwasser, S. and Sipser, M, Private-Coin vs. Public Coins in Interactive Proof Systems. The Complexity of Perfect Zero-Knowledge. Advances in Computing Research (ed. S. Micali) Vol. 5 (1989) 73-90
	Has90	J. Håstad, Pseudo-random generators under uniform assumptions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.395-404, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100270]
	Hoe63	Hoeffding, W.: Probability Inequalities for Sums of Bounded Random Variables. American Statistical Association Journal (1963) 13- 3O
	ILL89	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	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
	Nao90	Moni Naor, Bit commitment using pseudo-randomness (extended abstract), Proceedings on Advances in cryptology, p.128-136, July 1989, Santa Barbara, California, United States
	Ore87	Oren, Y.: On the Cunning Power of Cheating Verifiers. Proc. of FOCS'87 (1987) 472-482
	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	Ostrovsky, R. and Wigderson, M.: One-Way Functions are Essential for Non-Trivail Zero- Knowledge. Proc. of Israeli Symposium on Theory of Computing and Systems (1993) 3- 17
	Sip83	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 4

	Giovanni Di Crescenzo , Kouichi Sakurai , Moti Yung, On zero-knowledge proofs (extended abstract): “from membership to decision”, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.255-264, May 21-23, 2000, Portland, Oregon, United States
	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
	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

INDEX TERMS

Primary Classification:
G. Mathematics of Computing

Additional Classification:
E. Data

General Terms:
Theory, Verification

Collaborative Colleagues:

Tatsuaki Okamoto: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player