Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Full text

Pdf (3.04 MB)

Source

Journal of the ACM (JACM) archive
Volume 38 , Issue 3 (July 1991) table of contents

Pages: 690 - 728

Year of Publication: 1991

ISSN:0004-5411

Authors

Oded Goldreich	Technion, Haifa, Israel
Silvio Micali	Massachusetts Institute of Technology, Cambridge
Avi Wigderson	Hebrew Univ., Jerusalem, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 258, Citation Count: 80

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/116825.116852 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	AIELLO, W., GOLDWASSER, S., AND HASTAD, J. On the power of interaction. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 368-379.
	3	AIELLO, W, AND HASTAD, J. Perfect zero-knowledge languages can be recognized in two rounds. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 439-448.
	4	Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
	5	ALON, N., GALIL, Z.. AND YUNG, M. A fully polynomial simultaneous broadcast in the presence of faults. Unpublished manuscript, 1985.
	6	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]
	7	BABAI, L., KANTOR, W. M., AND LUKS, E.M. Computational complexity and classification of finite simple groups. In Proceedings of the 24th Annual IEEE Foundations of Computer Science. IEEE, New York, 1983, pp. 162-171.
	8	László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
	9	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]
	10	Josh Cohen Benaloh, Cryptographic capsules: a disjunctive primitive for interactive protocols, Proceedings on Advances in cryptology---CRYPTO '86, p.213-222, January 1987, Santa Barbara, California, United States
	11	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
	12	Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
	13	BLAK_eLY, G. R. Safeguarding cryptographic keys. In Proceedings of National Computer Conference, vol. 48. AFIPS Press, 1979, pp. 313- 317.
	14	R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
	15	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]
	16	Gilles Brassard , Claude Crépeau, Zero-knowledge simulation of Boolean circuits, Proceedings on Advances in cryptology---CRYPTO '86, p.223-233, January 1987, Santa Barbara, California, United States
	17	BRASSARD, G., AND CR~PZAU, C. Non-transitive transfer of confidence: A perfect zeroknowledge interactive protocol for SAT and beyond. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 188-195.
	18	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
	19	David Chaum, Demonstrating that a public predicate can be satisfied without revealing any information about how, Proceedings on Advances in cryptology---CRYPTO '86, p.195-199, January 1987, Santa Barbara, California, United States
	20	David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
	21	CHOR, B., GOLDWASSER, S., MICALI, S., AND AWERBUCH, B. Verifiable secret sharing and achieving simultaneity in the presence of faults. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1985, pp. 383-395.
	22	B. Chor , E. Kushilevitz, A zero-one law for Boolean privacy, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.62-72, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73013]
	23	COHEN, J. D., AND FISCHER, M. J. A robust and verifiable cryptographically secure election scheme. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. It~IEE. New York. 10~5. pp. 372-392.
	24	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	25	DIFFIE, W., AND HELLMAN, M.E. New directions in cryptography. IEEE Trans. Inf. Theory, IT-22, 6 (Nov. 1976), 644-654.
	26	Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
	27	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]
	28	Uriel Feige , Adi Shamir, Zero knowledge proofs of knowledge in two rounds, Proceedings on Advances in cryptology, p.526-544, July 1989, Santa Barbara, California, United States
	29	FELDMAN, P. A practical scheme for verifiable secret sharing. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 427-438.
	30	FISCHER, M., MICALI, S., RACKOFF, C., AND WITTENBERG, D.K. An oblivious transfer protocol equivalent to factoring. Unpublished manuscript, 1986.
	31	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]
	32	GALIL, Z., HABER, S., AND YUNG, M. A private interactive test of a Boolean predicate and minimum-knowledge public-key cryptosystems. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 360-371.
	33	Zvi Galil , Stuart Haber , Moti Yung, Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.135-155, August 16-20, 1987
	34	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	35	GARZY, M. R., JOHNSON, D. S., AND STOCKMEYER, L. Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1 (1976), 237-267.
	36	GOLDREICH, O. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript, 1985.
	37	GOLDREICH, O. Zero-knowledge and the design of secure protocols (an exposition). Tech. Rep. TR-480. Comput. Sci. Dept., Technion, Haifa, Israel, 1987.
	38	GOLDREICH, O. Towards a theory of average case complexity (a survey). Tech. Rep. TR-53I. Comput. Sci. Dept., Techmon, Haifa, Israel, 1988.
	39	GOLDREICH, O. A uniform-complexity treatment of encryption and zero-knowledge. Tech. Rep. TR-568. Comput. Sci. Dept., Technion, Haifa, Israel, 1989.
	40	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
	41	GOLDREICH, O., MANSOUR, Y., AND SIPSER, M. Interactive proof systems: Provers that never fail and random selection. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 449-461.
	42	GOLDREICH, O., MICALI, S., AND WIGDERSON, A. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 174-187.
	43	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
	44	GOLDRE1CH, O, AND OREN, Y. Definitions and properties of zero-knowledge proof systems. Tech. Rep. TR-610. Comput. Sci. Dept., Technion, Haifa, Israel, 1990.
	45	Oded Goldreich , Ronen Vainish, How to Solve any Protocol Problem - An Efficiency Improvement, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.73-86, August 16-20, 1987
	46	GOLDWASSER, S., AND MICALI, S. Probabllistic encryptlon. J. Comput. Syst. Sei. 28, 2 (1984), 270-299.
	47	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]
	48	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]
	49	S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
	50	GUREVICH, Y. Average case completeness. Tech. Rep. CRL-TR-03-88, Comput. Res. Lab., Univ. Michigan, Ann Arbor, Mich., 1988.
	51	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]
	52	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]
	53	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
	54	KARP, R.M. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, eds. Complexity of Computer Computations. Plenum Press, New York, 1972, pp. 85-103.
	55	KILIAN, J., MICALI, S., AND OSTROVSKY, R. Minimum resource zero-knowledge proofs. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1989, pp. 474-479.
	56	LEVlN, L.A. Universal search problems. Prob. Pere. Inf. 9 (1973), 115-116. Translated m Prob. Inf. Trans. 9 (1973), 265-266.
	57	Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
	58	Moni Naor, Bit commitment using pseudo-randomness (extended abstract), Proceedings on Advances in cryptology, p.128-136, July 1989, Santa Barbara, California, United States
	59	NISSAN, N., AND WIGDERSON, A. Hardness vs. randomness. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1988, pp. 2-11.
	60	OREN, Y. On the cunning power of cheating verifiers: Some observations about zero-knowledge proofs. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 462-471.
	61	M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
	62	T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
	63	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
	64	U. Schöning, Graph isomorphism is in the low hierarchy, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.114-124, February 1987, Passau, Germany
	65	Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
	66	STOCKMEYER, L.J. The polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977), 1-22.
	67	TOMPA, M., AND WOLL, H. Random self-reducibility and zero-knowledge interactive proofs of possession of information. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1987, pp. 472-482.
	68	YAO, A.C. Theory and applications of trapdoor functions. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 80-91.
	69	YAO, A.C. How to generate and exchange secrets. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 162-167.

CITED BY 80

	Wei Jiang , Chris Clifton , Murat Kantarcıoğlu, Transforming semi-honest protocols to ensure accountability, Data & Knowledge Engineering, v.65 n.1, p.57-74, April, 2008
	Rosario Gennaro, Achieving independence efficiently and securely, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.130-136, August 20-23, 1995, Ottowa, Ontario, Canada
	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
	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
	Joe Kilian , Erez Petrank, Concurrent and resettable zero-knowledge in poly-loalgorithm rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.560-569, July 2001, Hersonissos, Greece
	Glenn Durfee , Matt Franklin, Distribution chain security, Proceedings of the 7th ACM conference on Computer and communications security, p.63-70, November 01-04, 2000, Athens, Greece
	Ran Canetti , Joe Kilian , Erez Petrank , Alon Rosen, Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.570-579, July 2001, Hersonissos, Greece
	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
	Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996
	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
	Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States
	Yair Frankel , Peter Gemmell , Moti Yung, Witness-based cryptographic program checking and robust function sharing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.499-508, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Ran Canetti , Oded Goldreich , Shafi Goldwasser , Silvio Micali, Resettable zero-knowledge (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.235-244, May 21-23, 2000, Portland, Oregon, United States
	Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Uriel Feige , Magnús M. Halldórsson , Guy Kortsarz, Approximating the domatic number, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.134-143, May 21-23, 2000, Portland, Oregon, United States
	Adam R. Klivans , Dieter van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.659-667, May 01-04, 1999, Atlanta, Georgia, United States
	Joan Boyar , Gilles Brassard , René Peralta, Subquadratic zero-knowledge, Journal of the ACM (JACM), v.42 n.6, p.1169-1193, Nov. 1995
	Rosario Gennaro , Michael O. Rabin , Tal Rabin, Simplified VSS and fast-track multiparty computations with applications to threshold cryptography, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.101-111, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	Rosario Gennaro , Daniele Micciancio , Tal Rabin, An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products, Proceedings of the 5th ACM conference on Computer and communications security, p.67-72, November 02-05, 1998, San Francisco, California, United States
	Manuel Blum , Sampath Kannan, Designing programs that check their work, Journal of the ACM (JACM), v.42 n.1, p.269-291, Jan. 1995
	Alfredo De Santis , Yvo Desmedt , Yair Frankel , Moti Yung, How to share a function securely, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.522-533, May 23-25, 1994, Montreal, Quebec, Canada
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Jörg Rothe, Some facets of complexity theory and cryptography: A five-lecture tutorial, ACM Computing Surveys (CSUR), v.34 n.4, p.504-549, December 2002
	Stephen A. Fenner , Lance Fortnow , Ashish V. Naik , John D. Rogers, Inverting onto functions, Information and Computation, v.186 n.1, p.90-103, 10 October 2003
	Cynthia Dwork , Moni Naor , Omer Reingold , Larry Stockmeyer, Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998, Journal of the ACM (JACM), v.50 n.6, p.852-921, November 2003
	Oded Goldreich , Salil Vadhan , Avi Wigderson, On interactive proofs with a laconic prover, Computational Complexity, v.11 n.1/2, p.1-53, January 2003
	Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate probabilistically checkable proofs, Information and Computation, v.189 n.2, p.135-159, March 15, 2004
	Rosario Gennaro , Yuval Ishai , Eyal Kushilevitz , Tal Rabin, The round complexity of verifiable secret sharing and secure multicast, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.580-589, July 2001, Hersonissos, Greece
	Giovanni Di Crescenzo , Yuval Ishai , Rafail Ostrovsky, Non-interactive and non-malleable commitment, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.141-150, May 24-26, 1998, Dallas, Texas, United States
	Rosario Gennaro, A Protocol to Achieve Independence in Constant Rounds, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.636-647, July 2000
	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
	Danny Harnik , Moni Naor , Omer Reingold , Alon Rosen, Completeness in two-party secure computation: a computational view, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Moni Naor, Cryptography and mechanism design, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Journal of the ACM (JACM), v.51 n.6, p.851-898, November 2004
	Oded Goldreich, Concurrent zero-knowledge with timing, revisited, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Dan Gutfreund , Ronen Shaltiel , Amnon Ta-Shma, Uniform hardness versus randomness tradeoffs for Arthur-Merlin games, Computational Complexity, v.12 n.3-4, p.85-130, September 2004
	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
	André Adelsbach , Markus Rohe , Ahmad-Reza Sadeghi, Overcoming the obstacles of zero-knowledge watermark detection, Proceedings of the 2004 workshop on Multimedia and security, September 20-21, 2004, Magdeburg, Germany
	Lance Fortnow, Beyond NP: the work and legacy of Larry Stockmeyer, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ning Chen , Jia-Wei Rong, Memorizable interactive proof and zero-knowledge proof systems, Journal of Computer Science and Technology, v.19 n.6, p.936-941, November 2004
	David S. Johnson, The NP-completeness column, ACM Transactions on Algorithms (TALG), v.1 n.1, p.160-176, July 2005
	Ahmad-Reza Sadeghi , Christian Stüble, Property-based attestation for computing platforms: caring about properties, not mechanisms, Proceedings of the 2004 workshop on New security paradigms, September 20-23, 2004, Nova Scotia, Canada
	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
	Rafael Pass , Alon Rosen, New and improved constructions of non-malleable cryptographic protocols, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Yana Kortsarts , Jeffrey Rufinus, How (and why) to introduce Monte Carlo randomized algorithms into a basic algorithms course?, Journal of Computing Sciences in Colleges, v.21 n.2, p.195-203, December 2005
	Yana Kortsarts , Jeffrey Rufinus, Teaching the power of randomization using a simple game, ACM SIGCSE Bulletin, v.38 n.1, March 2006
	Boaz Barak , Yehuda Lindell , Salil Vadhan, Lower bounds for non-black-box zero knowledge, Journal of Computer and System Sciences, v.72 n.2, p.321-391, March 2006
	Peter Bro Miltersen , N. V. Vinodchandran, Derandomizing Arthur-Merlin games using hitting sets, Computational Complexity, v.14 n.3, p.256-279, January 2005
	Boaz Barak , Yehuda Lindell, Strict polynomial-time in simulation and extraction, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Scott Aaronson , Avi Wigderson, Algebrization: a new barrier in complexity theory, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	M. Burmester , E. Magkos , V. Chrissikopoulos, Uncoercible e-Bidding Games, Electronic Commerce Research, v.4 n.1-2, p.113-125, January-April 2004
	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
	Silvio Micali , Rafael Pass, Local zero knowledge, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Yuval Ishai , Eyal Kushilevitz , Yehuda Lindell , Erez Petrank, Black-box constructions for secure computation, 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
	Edith Hemaspaandra , Lane A. Hemaspaandra , Stanisław P. Radziszowski , Rahul Tripathi, Complexity results in graph reconstruction, Discrete Applied Mathematics, v.155 n.2, p.103-118, January, 2007
	Ken-ichi Kawarabayashi , Bojan Mohar, Graph and map isomorphism and all polyhedral embeddings in linear time, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Shafi Goldwasser , Dan Gutfreund , Alexander Healy , Tali Kaufman , Guy N. Rothblum, Verifying and decoding in constant depth, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Rafael Pass , Muthuramakrishnan Venkitasubramaniam, An efficient parallel repetition theorem for Arthur-Merlin games, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Mike Burmester , Yvo G. Desmedt , Fred Piper , Michael Walker, A General Zero-Knowledge Scheme, Designs, Codes and Cryptography, v.12 n.1, p.13-37, Sept. 1997
	Bernhard Jansen , Hari-Govind V. Ramasamy , Matthias Schunter, Policy enforcement and compliance proofs for Xen virtual machines, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA
	Oded Goldreich, A taxonomy of proof systems (part 2), ACM SIGACT News, v.25 n.1, p.22-30, March 1994
	Oded Goldreich, A taxonomy of proof systems (part 1), ACM SIGACT News, v.24 n.4, p.2-13, Dec. 1993
	Oded Goldreich, Probabilistic Proof Systems: A Primer, Foundations and Trends® in Theoretical Computer Science, v.3 n.1, p.1-91, January 2008
	Vicente Benjumea , Javier Lopez , Jose M. Troya, Anonymity analysis in credentials-based systems: A formal framework, Computer Standards & Interfaces, v.30 n.4, p.253-261, May, 2008
	Shafi Goldwasser , Yael Tauman Kalai , Guy N. Rothblum, Delegating computation: interactive proofs for muggles, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Huijia Lin , Rafael Pass, Non-malleability amplification, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Madhu Sudan, Probabilistically checkable proofs, Communications of the ACM, v.52 n.3, March 2009
	Andrew C. C. Yao , Frances F. Yao , Yunlei Zhao, A note on universal composable zero-knowledge in the common reference string model, Theoretical Computer Science, v.410 n.11, p.1099-1108, March, 2009
	Scott Aaronson , Avi Wigderson, Algebrization: A New Barrier in Complexity Theory, ACM Transactions on Computation Theory (TOCT), v.1 n.1, p.1-54, February 2009
	Iftach Haitner , Omer Reingold , Salil Vadhan , Hoeteck Wee, Inaccessible entropy, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Andrew c. c. Yao , Frances f. Yao , Yunlei Zhao, A note on the feasibility of generalised universal composability†, Mathematical Structures in Computer Science, v.19 n.1, p.193-205, February 2009
	Jan Hajny , Tomáš Pelka , Václav Zeman, Flexible authentication framework with bound authentication and authorization, WSEAS TRANSACTIONS on COMMUNICATIONS, v.8 n.1, p.143-152, January 2009
	Kamesh Namuduri, An active trust model based on zero knowledge proofs for airborne networks, Proceedings of the 5th Annual Workshop on Cyber Security and Information Intelligence Research: Cyber Security and Information Intelligence Challenges and Strategies, April 13-15, 2009, Oak Ridge, Tennessee
	Huijia Lin , Rafael Pass , Muthuramakrishnan Venkitasubramaniam, A unified framework for concurrent security: universal composability from stand-alone non-malleability, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Russell Impagliazzo , Valentine Kabanets , Antonina Kolokolova, An axiomatic approach to algebrization, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	R. Xue , D. Song , Z. Zhang , D. Feng, A Generic Scheme for Zero-Knowledge Sets, Proceeding of the 2005 conference on Applied Public Key Infrastructure: 4th International Workshop: IWAP 2005, p.249-263, May 09, 2005