Algebraic methods for interactive proof systems

ABSTRACT

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].

REFERENCES

• 1: ~AIELLO, W., GOLDWASSER, S., AND H~xSTAD, J. On the power of interaction. Combinatorica, ~10, 1 (1992), 3-25.
• 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: ~BABAI, L., AND FORTNOW, L. Arithmetization: a new method in structural complexity theory. ~Computat. Complex. 1 (1991), 41-66.
• 4: ~BABAI, L., FORTNOW, L. AND LUND, C. Non-deterministic exponential time has two-prover ~interactive protocols. Comp,tat. Complex. I (1991), 3-40.
• 5: 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]
• 6: Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
• 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: M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100225]
• 11: 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]
• 12: ~CAt, J., CONDON, A., AND LIPTON, R.J. PSPACE is provable by two provers in one round. In ~Proceedings of the 6th Annual Conference on Structure in Complexity Theory (Chicago, Ill., June ~30-July 3). IEEE, New York, 1991, pp. 110-115.
• 13: ~CHOR, B., GOLDREICH, O., AND H,~STAD, J. The random oracle hypothesis is false. ~Manuscript, Technion, Haifa, Israel, 1990.
• 14: 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]
• 15: ~FELDMAN, P. The optimum prover lives in PSPACE. Manuscript. M.I.T., Cambridge, Mass., ~1986.
• 16: Lance Fortnow , Carsten Lund, Interactive proof systems and alternating time-space complexity, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.263-274, February 1991, Hamburg, Germany
• 17: ~FORTNOW, L., ROMPEL, J., AND SIPSER, M. On the power of multi-prover interactwe ~protocols. In Proceedings of the 3rd Con}erence on Structure zn Complexity Theory (Washington, ~D.C., June 14-17). IEEE, New York, 1988, pp. 156 161.
• 18: Lance Fortnow , Michael Sipser, Are there interactive protocols for CO-NP languages?, Information Processing Letters, v.28 n.5, p.249-251, Aug. 12, 1988 [doi>10.1016/0020-0190(88)90199-8]
• 19: ~FURER, M., GOLDREICH, O., MANSOUR, Y., SIPSER, M., AND ZACHOS, S. On completeness ~and soundness in interactive proof systems. In S. Micali, ed. Randomness and Computation, ~(volume 5 of Advances m Compzmng Research). JAI Press, Greenwich, Conn. 1989, pp. ~429-442.
• 20: ~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 IEEE ~Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 174 187.
• 21: 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]
• 22: ~GOLDWASSER, S. AND SIPSER, M. Private coins versus public coins in interactive proof ~systems. In S. Micali, ed. Randomness and Compzttatzon, (volume 5 of AdL,ances bz Computing ~Research). JAI Press, Greenwich, Conn. 1989, pp. 73-90.
• 23: 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
• 24: Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804678]
• 25: ~LIPTON, R. New directions in testing. In J. Feigenbaum and M. Merntt, eds. Dtstributed ~Computing and Cr37~tography (volume 2 of DIMACS Se~es in Dtscrete Mathematics and ~Theoretical Computer Science). American Mathematical Society, Providence, R.I., 1991, pp. ~191-202.
• 26: ~NIVEN, I., AND ZUCKERMAN, H. S. An tntroductzon to the theory of numbers 4th ed., Wiley, ~New York, 1980, pp. 224-225.
• 27: ~PRATt, V. Every prime has a succinct certificate. SIAMJ. Comput. 4 (1975), 214-220.
• 28: Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
• 29: A. Shen, IP = SPACE: simplified proof, Journal of the ACM (JACM), v.39 n.4, p.878-880, Oct. 1992 [doi>10.1145/146585.146613]
• 30: Janos Simon, On Some Central Problems in Computational Complexity, Cornell University, Ithaca, NY, 1975
• 31: ~SOLOVAY, R., AND STRASSEN, V. h fast Monte-Carlo test for primality. SIAM Jr. Conzput. 6 ~(1977), 84-85. See also erratum 7 (1978), I18.
• 32: ~TODA, S. On the computational power of PP and ~ P. In Proceedings of the 30th iEEE ~Symposntm on Foundatzons of Computer Science. IEEE, New York, 1989, pp. 514-519.
• 33: ~VALIANT, L. The complexity of computing the permanent. Theoret. Conzput. Scz 8 (1979), ~189-201.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Relativized computation; Probabilistic computation; Relations among modes**
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies; Relations among complexity classes

General Terms:
Theory

Keywords:
interactive proof systems