Journal of the ACM Bibliography

Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks] -- data

Selected papers that cite this one

• D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway. Locally random reductions: Improvements and applications. Journal of Cryptology, 10(1):17-36, Winter 1997.

• Mihir Bellare and Shafi Goldwasser. The complexity of decision versus search. SIAM Journal on Computing, 23(1):97-119, February 1994.

• Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and nonapproximability -- towards tight results. SIAM Journal on Computing, 27(3):804-915, June 1998.

• Mihir Bellare and Moti Yung. Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation. Journal of Cryptology, 9(3):149-166, Summer 1996.

• Josh Benaloh and Dwight Tuinstra. Receipt-free secret-ballot elections (extended abstract). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 544-553, Montréal, Québec, Canada, 23-25 May 1994.

• Manuel Blum and Sampath Kannan. Designing programs that check their work. Journal of the ACM, 42(1):269-291, January 1995.

• Joan Boyar, Gilles Brassard, and René Peralta. Subquadratic zero-knowledge. Journal of the ACM, 42(6):1169-1193, November 1995.

• Joan Boyar, Carsten Lund, and René Peralta. On the communication complexity of zero-knowledge proofs. Journal of Cryptology, 6(2):65-85, 1993.

• Mike Burmester, Yvo G. Desmedt, Fred Piper, and Michael Walker. A general zero-knowledge scheme. Designs, Codes and Cryptography, 12(1):13-37, September 1997.

• Ran Canetti and Rosario Gennaro. Incoercible multiparty computation (extended abstract). In 37th Annual Symposium on Foundations of Computer Science, pages 504-513, Burlington, Vermont, 14-16 October 1996. IEEE.

• Anne Condon and Richard Ladner. Interactive proof systems with polynomially bounded strategies. Journal of Computer and System Sciences, 50(3):506-518, June 1995.

• Giovanni Di Crescenzo, Kouichi Sakurai, and Moti Yung. Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols. In 15th Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 511-521, Paris France, 25-27 February 1998. Springer.

• Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, March 1996.

• Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57(2):187-199, October 1998.

• Yair Frankel, Peter Gemmell, and Moti Yung. Witness-based cryptographic program checking and robust function sharing. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 499-508, Philadelphia, Pennsylvania, 22-24 May 1996.

• Oded Goldreich. A uniform-complexity treatment of encryption and zero-knowledge. Journal of Cryptology, 6(1):21-53, 1993.

• Oded Goldreich, Shafi Goldwasser, and Nathan Linial. Fault-tolerant computation in the full information model. SIAM Journal on Computing, 27(2):506-544, March 1998.

• Oded Goldreich and Eyal Kushilevitz. A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. Journal of Cryptology, 6(2):97-116, 1993.

• Oded Goldreich and Ariel Kahan. How to construct constant-round zero-knowledge proof systems for np. Journal of Cryptology, 9(3):167-189, Summer 1996.

• Oded Goldreich and Hugo Krawczyk. On the composition of zero-knowledge proof systems. SIAM Journal on Computing, 25(1):169-192, February 1996.

• Oded Goldreich, Rafail Ostrovsky, and Erez Petrank. Computational complexity and knowledge complexity (extended abstract). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 534-543, Montréal, Québec, Canada, 23-25 May 1994.

• Oded Goldreich, Rafail Ostrovsky, and Erez Petrank. Computational complexity and knowledge complexity. SIAM Journal on Computing, 27(4):1116-1141, August 1998.

• Shafi Goldwasser. New directions in cryptography: Twenty some years later (or Cryptography and complexity theory: A match made in heaven). In 38th Annual Symposium on Foundations of Computer Science, pages 314-324, Miami Beach, Florida, 20-22 October 1997. IEEE.

• Toshiya Itoh, Masafumi Hoshi, and Shigeo Tsujii. A low communication competitive interactive proof system for promised quadratic residuosity. Journal of Cryptology, 9(2):101-109, Spring 1996.

• Toshiya Itoh, Yuji Ohta, and Hiroki Shizuya. A language-dependent cryptographic primitive. Journal of Cryptology, 10(1):37-49, Winter 1997.

• Torben Pryds Pedersen and Birgit Pfitzmann. Fail-stop signatures. SIAM Journal on Computing, 26(2):291-330, April 1997.

• Erez Petrank and Gábor Tardos. On the knowledge complexity of NP. In 37th Annual Symposium on Foundations of Computer Science, pages 494-503, Burlington, Vermont, 14-16 October 1996. IEEE.

• Amit Sahai and Salil P. Vadhan. A complete promise problem for statistical zero-knowledge. In 38th Annual Symposium on Foundations of Computer Science, pages 448-457, Miami Beach, Florida, 20-22 October 1997. IEEE.

• Alfredo De Santis, Yvo Desmedt, Yair Frankel, and Moti Yung. How to share a function securely (extended summary). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 522-533, Montréal, Québec, Canada, 23-25 May 1994.

Selected references

• William Aiello, Shafi Goldwasser, and Johan Hastad. On the power of interaction. In 27th Annual Symposium on Foundations of Computer Science, pages 368-379, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.

• William Aiello and Johan Hastad. Perfect zero-knowledge languages can be recognized in two rounds. In 28th Annual Symposium on Foundations of Computer Science, pages 439-448, Los Angeles, California, 12-14 October 1987. IEEE.

• Werner Alexi, Benny Chor, Oded Goldreich, and Claus P. Schnorr. RSA/Rabin bits are 1/2 + 1/poly(log N) secure. In 25th Annual Symposium on Foundations of Computer Science, pages 449-457, Singer Island, Florida, 24-26 October 1984. IEEE.

• László Babai. Trading group theory for randomness. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 421-429, Providence, Rhode Island, 6-8 May 1985.

• L. Babai, W. M. Kantor, and E. M. Luks. Computational complexity and the classification of finite simple groups. In 24th Annual Symposium on Foundations of Computer Science, pages 162-171, Tucson, Arizona, 7-9 November 1983. IEEE.

• Mihir Bellare, Silvio Micali, and Rafail Ostrovsky. Perfect zero-knowledge in constant rounds. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 482-493, Baltimore, Maryland, 14-16 May 1990.

• Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 1-10, Chicago, Illinois, 2-4 May 1988.

• Gilles Brassard and Claude Crepeau. Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond. In 27th Annual Symposium on Foundations of Computer Science, pages 188-195, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.

• David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 11-19, Chicago, Illinois, 2-4 May 1988.

• Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In 26th Annual Symposium on Foundations of Computer Science, pages 383-395, Portland, Oregon, 21-23 October 1985. IEEE.

• Benny Chor and Eyal Kushilevitz. A zero-one law for Boolean privacy (extended abstract). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 62-72, Seattle, Washington, 15-17 May 1989.

• Josh D. Cohen and Michael J. Fischer. A robust and verifiable cryptographically secure election scheme (extended abstract). In 26th Annual Symposium on Foundations of Computer Science, pages 372-382, Portland, Oregon, 21-23 October 1985. IEEE.

• Stephen A. Cook. The complexity of theorem-proving procedures. In Conference Record of Third Annual ACM Symposium on Theory of Computing, pages 151-158, Shaker Heights, Ohio, 3-5 1971 1971.

• Paul Feldman. A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science, pages 427-437, Los Angeles, California, 12-14 October 1987. IEEE.

• Lance Fortnow. The complexity of perfect zero-knowledge (extended abstract). In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 204-209, New York City, 25-27 May 1987.

• Zvi Galil, Stuart Haber, and Moti Yung. A private interactive test of a Boolean predicate and minimum-knowledge public-key cryptosystems (extended abstract). In 26th Annual Symposium on Foundations of Computer Science, pages 360-371, Portland, Oregon, 21-23 October 1985. IEEE.

• Oded Goldreich, Yishay Mansour, and Michael Sipser. Interactive proof systems: Provers that never fail and random selection (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, pages 449-461, Los Angeles, California, 12-14 October 1987. IEEE.

• Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In 27th Annual Symposium on Foundations of Computer Science, pages 174-187, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.

• Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 218-229, New York City, 25-27 May 1987.

• Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 59-68, Berkeley, California, 28-30 May 1986.

• Johan Håstad. Pseudo-random generators under uniform assumptions. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 395-404, Baltimore, Maryland, 14-16 May 1990.

• Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 12-24, Seattle, Washington, 15-17 May 1989.

• Joe Kilian, Silvio Micali, and Rafail Ostrovsky. Minimum resource zero-knowledge proofs (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 474-479, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Noam Nisan and Avi Wigderson. Hardness vs. randomness (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 2-11, White Plains, New York, 24-26 October 1988. IEEE.

• Yair Oren. On the cunning power of cheating verifiers: Some observations about zero knowledge proofs (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, pages 462-471, Los Angeles, California, 12-14 October 1987. IEEE.

• Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 73-85, Seattle, Washington, 15-17 May 1989.

• Martin Tompa and Heather Woll. Random self-reducibility and zero knowledge interactive proofs of possession of information. In 28th Annual Symposium on Foundations of Computer Science, pages 472-482, Los Angeles, California, 12-14 October 1987. IEEE.

• Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80-91, Chicago, Illinois, 3-5 November 1982. IEEE.

• Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In 27th Annual Symposium on Foundations of Computer Science, pages 162-167, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.

Shortcuts: