Making zero-knowledge provers efficient

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Making zero-knowledge provers efficient

Full text

Pdf (1.34 MB)

Source

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

Victoria, British Columbia, Canada

Pages: 711 - 722

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Mihir Bellare	High Performance Computing and Communications, IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY
Erez Petrank	Department of Computer Science, Technion, Haifa, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 6

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/129712.129781 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	W. AIELLO AND J. HASTAD. Perfect Zero-Knowledge can be Recognized in Two Rounds. FOCS 87.
	2	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]
	3	L. BABAI, L. FORTNOW AND C. LUND. Non- Deterministic Exponential Time has Two-Prover Interactive Protocols. FOCS 90.
	4	Richard Beigel , Mihir Bellare , Joan Feigenbaum , Shafi Goldwasser, Languages that are easier than their proofs, Proceedings of the 32nd annual symposium on Foundations of computer science, p.19-28, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185343]
	5	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]
	6	M. BELLARE AND E. PETRANK. Making Zero- Knowledge Provers Efficient. Technical Report, Computer Science Department, Technion, Haifa, Israel.
	7	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
	8	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 [doi>10.1145/62212.62223]
	9	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]
	10	L. CARTER AND M. WEGMAN. Universal Classes of Hash Functions. J. Computer and System Sciences 18, 143-154 (1979).
	11	U. FEIGE. Interactive Proofs. M.Sc Thesis, Weizmann Institute of Science. August 1987.
	12	L. FORTNOW. The Complexity of Perfect Zero- Knowledge. Advances in Computing Research (ed. S. MicalO Vol. lS (1989).
	13	Oded Goldreich , Hugo Krawczyk, On the composition of zero-knowledge proof systems, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.268-282, July 1990, Warwick University, England
	14	O. GOLDREICH, Y. MANSOUR AND M. SIPSER. Interactive Proof Systems" Provers that never Fail and Random Selection. FOCS 87.
	15	O. GOLDREICH AND Y. OREN. Definitions and Properties of Zero-Knowledge Proof Systems. Technical Report #570, Technion (1989).
	16	Oded Goldreich , Erez Petrank, Quantifying knowledge complexity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.59-68, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185349]
	17	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]
	18	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]
	19	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]
	20	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
	21	M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
	22	C. LUND, L. FORTNOW, H. KARLOFF AND N. NISAN. Algebraic Methods for Interactive Proof Systems. FOCS 9O.
	23	Y. OREN. On The Cunning Power of Cheating Verifiers: Some Observations About Zero Knowledge Proofs. FOCS 87.
	24	R. OSTROVSKY. One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs. Structures 1991.
	25	R. OSTROVSKY, R. VENKATESAN AND M. YUNG. 0n the Complexity of Asymmetric Games. Manuscript (1990).
	26	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]
	27	Larry Stockmeyer, The complexity of approximate counting, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.118-126, December 1983 [doi>10.1145/800061.808740]
	28	M. TOMPA AND H. WOLL. Random Self-Reducibility and Zero-Knowledge Proofs of Possession of Information. FOCS 87.

CITED BY 6

	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
	William Aiello , Mihir Bellare , Ramarathnam Venkatesan, Knowledge on the average—perfect, statistical and logarithmic, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.469-478, May 29-June 01, 1995, Las Vegas, Nevada, 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
	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
	Amos Beimel , Paz Carmi , Kobbi Nissim , Enav Weinreb, Private approximation of search problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	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