On Interactive Proofs with a Laconic Prover

1. William Aiello and Johan Håstad. Statistical zero-knowledge languages can be recognized in two rounds. Journal of Computer and System Sciences, 42(3):327–345, June 1991.

   Article  MATH  MathSciNet  Google Scholar 

2. V. Arvind and J. Köbler. On resource-bounded measure and pseudorandomness. In Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 235–249. LNCS 1346, Springer-Verlag, 1997.

   Chapter  Google Scholar 

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

   Google Scholar 

4. László Babai and Shlomo Moran. Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36:254–276, 1988.

   Article  MATH  MathSciNet  Google Scholar 

5. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and Nonapproximability—towards tight results. SIAM Journal on Computing, 27(3):804–915 (electronic), 1998.

   Article  MATH  MathSciNet  Google Scholar 

6. Ravi B. Boppana, Johan Håstad, and Stathis Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25:127–132, 1987.

   Article  MATH  MathSciNet  Google Scholar 

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

   Article  MATH  MathSciNet  Google Scholar 

8. Lance Fortnow. The complexity of perfect zero-knowledge. In Silvio Micali, editor, Advances in Computing Research, volume 5, pages 327–343. JAC Press, Inc., 1989.

   Google Scholar 

9. Oded Goldreich. Modern Cryptography, Probabilistic Proofs, and Pseudorandomness. Number 17 in Algorithms and Combinatorics. Springer-Verlag, 1999.

   Google Scholar 

10. Oded Goldreich and Shafi Goldwasser. On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences, 60(3):540–563, 2000.

    Article  MATH  MathSciNet  Google Scholar 

11. Oded Goldreich and Johan Håstad. On the complexity of interactive proofs with bounded communication. Information Processing Letters, 67(4):205–214, 1998.

    Article  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

13. 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(1):691–729, 1991.

    MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

15. Oded Goldreich and Erez Petrank. Quantifying knowledge complexity. Computational Complexity, 8(1):50–98, 1999.

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

17. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Silvio Micali, editor, Advances in Computing Research, volume 5, pages 73–90. JAC Press, Inc., 1989.

    Google Scholar 

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

    Google Scholar 

19. Adam R. Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, pages 659–667, Atlanta, 1-4 May 1999.

    Google Scholar 

20. Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859–868, October 1992.

    Article  MATH  MathSciNet  Google Scholar 

21. Peter Bro Miltersen and N.V. Vinodchandran. Derandomizing Arthur-Merlin games using hitting sets. In 40th Annual Symposium on Foundations of Computer Science, New York, NY, 17-19 October 1999. IEEE.

    Google Scholar 

22. Tatsuaki Okamoto. On relationships between statistical zero-knowledge proofs. Journal of Computer and System Sciences, 60(1):47–108, February 2000.

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

25. Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869–877, October 1992.

    Article  MATH  MathSciNet  Google Scholar 

26. Michael Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997.

    Google Scholar 

27. Alan Tucker. Applied combinatorics. John Wiley & Sons Inc., New York, third edition, 1995.

    MATH  Google Scholar 

28. Salil Vadhan. Probabilistic proof systems I: Interactive and zero-knowledge proofs. Lecture Notes from the IAS/PCMI Graduate Summer School on Computational Complexity, August 2000. Available from http://eecs.harvard.edu/~salil/.

Download references