Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: Joan Boyar, Gilles Brassard, and René Peralta. Subquadratic zero-knowledge. In 32nd Annual Symposium on Foundations of Computer Science, pages 69-78, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks] -- security and protection; D.4.6 [Operating Systems]: Security and Protection -- cryptographic controls; E.3 [Data Encryption]; F.0 [General]; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- alternation and nondeterminism, interactive computation, probabilistic computation; F.1.3 [Computation by Abstract Devices]: Complexity Classes; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems -- computations on matrices; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- complexity of proof procedures, computations on discrete structures; F.2.3 [Analysis of Algorithms and Problem Complexity]: Tradeoffs among Complexity Measures; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic -- proof theory; G.3 [Probability and Statistics] -- probabilistic algorithms; K.4.1 [Computers and Society]: Public Policy Issues -- privacy

General Terms: Algorithms, Security, Theory

Additional Key Words and Phrases: Bit commitment, circuit evaluation, communication complexity, cryptography, interactive proofs, matrix multiplication, non-averaging sets, probabilistic algorithms, proof systems, randomness, zero knowledge

Selected papers that cite this one

• Ronald Cramer and Ivan Damgård. Linear zero-knowledge -- a note on efficient zero-knowledge proofs and arguments. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 436-445, El Paso, Texas, 4-6 May 1997.

Selected references

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 21-31, New Orleans, Louisiana, 6-8 May 1991.

• Eric Bach. Realistic analysis of some randomized algorithms. Journal of Computer and System Sciences, 42(1):30-53, February 1991.

• Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 103-112, Chicago, Illinois, 2-4 May 1988.

• Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850-864, November 1984.

• Joan F. Boyar, Stuart A. Kurtz, and Mark W. Krentel. A discrete logarithm implementation of perfect zero-knowledge blobs. Journal of Cryptology, 2(2):63-76, 1990.

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

• 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.

• Gilles Brassard and Claude Crépeau. Zero-knowledge simulation of Boolean circuits. In A. M. Odlyzko, editor, Advances in Cryptology -- CRYPTO '86, volume 263 of Lecture Notes in Computer Science, pages 223-233, 11-15 August 1986. Springer-Verlag, 1987.

• Gilles Brassard, David Chaum, and Claude Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156-189, October 1988.

• David Chaum. Demonstrating that a public predicate can be satisfied without revealing any information about how. In A. M. Odlyzko, editor, Advances in Cryptology -- CRYPTO '86, volume 263 of Lecture Notes in Computer Science, pages 195-199, 11-15 August 1986. Springer-Verlag, 1987.

• David Chaum, Ivan B. Damgård, and Jeroen van de Graaf. Multiparty computations ensuring privacy of each party's input and correctness of the result. In Carl Pomerance, editor, Advances in Cryptology -- CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 87-119, 16-20 August 1987. Springer-Verlag, 1988.

• D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251-280, March 1990.

• Ivan Bjerre Damgård. On the randomness of Legendre and Jacobi sequences. In S. Goldwasser, editor, Advances in Cryptology -- CRYPTO '88, volume 403 of Lecture Notes in Computer Science, pages 163-172, 21-25 August 1988. Springer-Verlag, 1990.

• Uriel Feige, Amos Fiat, and Adi Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1(2):77-94, 1988.

• Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 308-317, St. Louis, Missouri, 22-24 October 1990. IEEE.

• Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):691-729, July 1991.

• Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270-299, April 1984.

• Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, February 1989.

• Jeroen van de Graaf and René Peralta. A simple and secure way to show the validity of your public key. In Carl Pomerance, editor, Advances in Cryptology -- CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 128-134, 16-20 August 1987. Springer-Verlag, 1988.

• Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 723-732, Victoria, British Columbia, Canada, 4-6 May 1992.

• Joe Kilian. On the complexity of bounded-interaction and noninteractive zero-knowledge proofs. In 35th Annual Symposium on Foundations of Computer Science, pages 466-477, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

• 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.

• Moni Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151-158, 1991.

• Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 213-223, Baltimore, Maryland, 14-16 May 1990.

• Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Non-interactive zero-knowledge proof systems. In Carl Pomerance, editor, Advances in Cryptology -- CRYPTO '87, volume 293 of Lecture Notes in Computer Science, pages 52-72, 16-20 August 1987. Springer-Verlag, 1988.

• 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.

Shortcuts: