Finite state verifiers I: the power of interaction

ABSTRACT

An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown: (1) IPSs in which the verifier uses private randomization are strictly more powerful than IPSs in which the random choices of the verifier are made public to the prover. (2) IPSs in which the verifier uses public randomization are strictly more powerful than 2pfa's alone, that is, without a prover. (3) Every language which can be accepted by some deterministic Turing machine in exponential time can be accepted by some IPS. Additional results concern two other classes of verifiers: 2pfa's that halt in polynomial expected time, and 2-way probabilistic pushdown automata that halt in polynomial time. In particular, IPSs with verifiers in the latter class are as powerful as IPSs where verifiers are polynomial-time probabilistic Turing machines. In a companion paper [7], zero knowledge IPSs with 2pfa verifiers are investigated.

REFERENCES

• 1: 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]
• 2: ~BRODER, A. Generating random spanning trees. In Proceedings of tile 30th 1EEE Symposium ~on Foundations of Computer Sctence. IEEE, New York, 1989, pp. 442-447.
• 3: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 4: ~CONr)ON, A. Computational models of games. Ph.D. dissertation, Tech. Rep. 87-04-04. ~Computer Science Dept., Univ. Washington, Seattle, Wash., 1987.
• 5: Anne Condon , Richard E. Ladner, Probabilistic games automata, Journal of Computer and System Sciences, v.36 n.3, p.452-489, June 1988 [doi>10.1016/0022-0000(88)90038-4]
• 6: ~CONDON, A., AND LIPTON, R.J. On the complexity of space bounded interactive proofs ~(extended abstract). In Proceedings of the 30th IEEE Symposium on Foundations of Computer ~ Science. IEEE, New York, 1989, pp. 462-467.
• 7: Cynthia Dwork , Larry Stockmeyer, Finite state verifiers II: zero knowledge, Journal of the ACM (JACM), v.39 n.4, p.829-858, Oct. 1992 [doi>10.1145/146585.146601]
• 8: Cynthia Dwork , Larry Stockmeyer, A time complexity gap for two-way probabilistic finite-state automata, SIAM Journal on Computing, v.19 n.6, p.1011-1123, Dec. 1990 [doi>10.1137/0219069]
• 9: Rusins Freivalds, Probabilistic Two-Way Machines, Proceedings on Mathematical Foundations of Computer Science, p.33-45, August 31-September 04, 1981
• 10: ~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.
• 11: 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]
• 12: 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]
• 13: Albert G Greenberg , Alan Weiss, A lower bound for probabilistic algorithms for finite state machines, Journal of Computer and System Sciences, v.33 n.1, p.88-105, Aug. 1986 [doi>10.1016/0022-0000(86)90045-0]
• 14: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 15: Jãnis Kaņeps , Rūsiņš Freivalds, Running time to recognize nonregular languages by 2-way probabilistic automata, Proceedings of the 18th international colloquium on Automata, languages and programming, p.174-185, June 1991, Madrid, Spain
• 16: ~K~L~AN, J. Zero-knowledge with log-space verifiers. In Proceedings oJ the 29th 1LEE ~Symposmm on Foundations of Compttter Science. IEEE, New York, 1988, pp. 25-35.
• 17: ~LEIGHTON, F. T., AND RIVEST, R.L. The Markov chain tree theorem. Rep. MIT/LCS/TM- ~249. Laboratory for Computer Scmnce. MIT, Cambridge, Mass., 1983.
• 18: F T Leighton , R L Rivest, Estimating a probability using finite memory, IEEE Transactions on Information Theory, v.32 n.6, p.733-742, Nov. 1986 [doi>10.1109/TIT.1986.1057250]
• 19: ~LIPTON, R.J. Recursively enumerable languages have finite state interactive proofs. Rep. ~CS-TR-213-89, Computer Science Dept., Princeton Univ., Princeton, N.J., 1989.
• 20: ~LUND, C., FORTNOW, L., KARLOFF, H., AND NISAN, N. Algebraic methods for interactive ~ proof systems. In Proceedings' of the 31th IEEE Symposium on Fozmdattons of Computer ~ Science. IEEE, New York, 1990, pp. 2 10.
• 21: ~RAmN, M.O. Probabilistic automata. Inf. Contr. 6 (1963), 230-245.
• 22: ~REIF, J. The complexity of two-player games of incomplete information. J. Comput. Svst. ~Sci. 29 (1984), 274 301.
• 23: ~SENETA, E. Non-Negative Matrices and Markov Chains. 2nd Ed. Sprmger-Verlag, New York, ~1981.
• 24: ~SHAMm, A. IP = PSPACE. In Proceedings of the 31th IEEE Symposium on Foundations of ~Computer Science. IEEE, New York, 1990, pp. 11-15.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism; Probabilistic computation; Interactive and reactive computation
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Theory, Verification

Keywords:
Arthur-Merlin games, complexity theory, finite state automata, interactive proof systems, probabilistic automata