On zero-knowledge proofs (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

On zero-knowledge proofs (extended abstract): “from membership to decision”

Full text

Pdf (1.21 MB)

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: 255 - 264

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Giovanni Di Crescenzo	Telcordia Technologies Inc., 445 South Street, Morristown, NJ
Kouichi Sakurai	Dept. of Computer Science, Kyushu University, Fukuoka 812-8581, Japan
Moti Yung	CertCo, New York, NY

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): 27, Citation Count: 1

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.335336 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	M. Abadi , J. Feigenbaum , J. Kilian, On hiding information from an oracle, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.195-203, January 1987, New York, New York, United States [doi>10.1145/28395.28417]
	2	Mihir Bellare , Oded Goldreich, On Defining Proofs of Knowledge, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.390-420, August 16-20, 1992
	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	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
	5	M. Blum, Coin Flipping by Phone, IEEE Spring COM- PCOM, pp. 133--137, 1982.
	6	M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
	7	J. Boyar, K. Friedl, and C. Lund, Practical Zero- Knowledge Proofs: Giving Hints and Using Deficiencies, Journal of Cryptology, n. 4, 1991.
	8	I. Dasnga~d, Interactive Hashing can simplify Zero- Knowledge Protocol Design without Complexity Assumptions, in Proceedings of CRYPTO 92.
	9	A. De Santis, G. Di Crescenzo, G. Persiano and M. Yung, On Monotone Formula Closure of SZK, in Proceedings of FOCS 94.
	10	Alfredo De Santis , Giovanni Di Crescenzo , Giuseppe Persiano , Moti Yung, Image Density is Complete for Non-Interactive-SZK (Extended Abstract), Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.784-795, July 13-17, 1998
	11	G. Di Crescenzo , R. Impagliazzo, Proofs of Membership vs. Proofs of Knowledge, Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity, p.34, June 15-18, 1998
	12	Giovanni Di Crescenzo , Kouichi Sakurai , Moti Yung, Zero-knowledge proofs of decision power: new protocols and optimal round-complexity, Proceedings of the First International Conference on Information and Communication Security, p.17-27, November 11-14, 1997
	13	Giovanni Di Crescenzo , Kouichi Sakurai , Moti Yung, Result-Indistinguishable Zero-Knowledge Proofs: Increased Power and Constant-Round Protocols, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.511-521, February 25-27, 1998
	14	Giovanni Di Crescenzo , Kouichi Sakurai , Moti Yung, Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently while Concealing it, Proceedings of the 9th International Symposium on Algorithms and Computation, p.59-68, December 14-16, 1998
	15	U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
	16	Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
	17	Zvi Galil , Stuart Haber , Moti Yung, Minimum-knowledge interactive proofs for decision problems, SIAM Journal on Computing, v.18 n.4, p.711-739, Aug. 1989 [doi>10.1137/0218049]
	18	O. Goldreich and E. Kushilevitz, A Perfect Zero- Knowledge Proof System for a Problem Equivalent to Discrete Logarithm, in Journal of Cryptology, 1993.
	19	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]
	20	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
	21	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]
	22	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
	23	T. Itoh, Y. Ohta, and H. Shizuya, A Language- Dependent Cryptographic Primitive, in Journal of Cryptology, vol. 10, n. 1, 1997, pp. 37-49.
	24	M. Naor, Bit Commitment using Pseudo-Randomness, in Proceedings of CRYPTO 91.
	25	Moni Naor , Rafail Ostrovsky , Ramarathnam Venkatesan , Moti Yung, Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions (Extended Abstract), Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.196-214, August 16-20, 1992
	26	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	27	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]
	28	It. Ostrovsky and A. Wigderson, One Way Functions are Essential for Non-2}~ivial Zero Knowledge, in Proceedings of ISTCS 93.
	29	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
	30	M. Tompa and H. Woll, Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information, in Proceedings of FOCS 87.
	31	Moti Yung, Zero-knowledge proofs of computational power (extended summary), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.196-207, November 1990, Houthalen, Belgium