Interactive proof system

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is all-powerful, with unlimited computational resources while the verifier has bounded computation power. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

All interactive proof systems have two requirements:

Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
Soundness: if the statement is false, no prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, except with some small probability.

Notice that we don't care what happens if the verifier is dishonest; we trust the verifier.

The specific nature of the system, and so the complexity class of languages it can recognize, depends on what sort of bounds are put on the verifier, as well as what abilities it is given — for example, most interactive proof systems depend critically on the verifier's ability to make random choices. It also depends on the nature of the messages exchanged — how many and what they can contain. Interactive proof systems have been found to have some surprisingly profound implications for traditional complexity classes defined using only one machine. The main complexity classes (really, hierarchies of complexity classes) defined using interactive proof systems are AM, MA, IP, and PCP.

Contents

1 NP

2 Arthur-Merlin and Merlin-Arthur protocols

3 Public coins versus private coins

NP

The familiar complexity class NP may be viewed as a very simple interactive proof system. In this system, the verifier is a deterministic, polynomial-time machine (a P machine). The protocol is:

The prover looks at the input and computes the solution using its unlimited power and returns a polynomial-size proof certificate.
The verifier verifies that the certificate is valid in deterministic polynomial time. If it is valid, it accepts; otherwise, it rejects.

In the case where a valid proof certificate exists, the prover is always able to make the verifier accept by giving it that certificate. In the case where there is no valid proof certificate, however, the input is not in the language, and no prover, however malicious it is, can convince the verifier otherwise, because any proof certificate will be rejected.

Arthur-Merlin and Merlin-Arthur protocols

Main article: Arthur-Merlin protocol

Although NP may be viewed as using interaction, it wasn't until 1985 that the concept of computation through interaction was conceived.¹ It was then that László Babai published "Trading group theory for randomness", a paper defining the Arthur-Merlin (AM) class hierarchy. In this presentation, Arthur (the verifier) is a probabilistic, polynomial-time machine, while Merlin (the prover) has unbounded resources.

The class MA in particular is a simple generalization of the NP interaction above in which the verifier is probabilistic instead of deterministic. Also, instead of requiring that the verifier always accept valid certificates and reject invalid certificates, we are more lenient:

If the string is in the language, the prover must be able to give a certificate such that the verifier will accept with probability at least 2/3 (depending on the verifier's random choices).
If the string is not in the language, no prover, however malicious, will be able to convince the verifier to accept the string with probability exceeding 1/3.

This machine is potentially more powerful than an ordinary NP interaction protocol, and the certificates are no less practical to verify, since BPP algorithms are practical (see BPP). We'll come back to Babai's other classes later.

Public coins versus private coins

Shortly after Babai defined his proof system for MA, Shafi Goldwasser et al. published a draft of a paper defining the interactive proof system IP[f(n)]. This has the same machines as the MA protocol, except that f(n) rounds are allowed for an input of size n. In each round, the verifier performs computation and passes a message to the prover, and the prover performs computation and passes information back to the verifier. At the end the verifier must make its decision. For example, in an IP[3] protocol, the sequence would be VPVPVPV, where V is a verifier turn and P is a prover turn.

In Arthur-Merlin protocols, Babai defined a similar class AM[f(n)] which allowed f(n) rounds, but he put one extra condition on the machine: the verifier must show the prover all the random bits it uses in its computation. The result is that the verifier cannot "hide" anything from the prover, because the prover is powerful enough to simulate everything the verifier does if it knows what random bits it used. We call this a public coin protocol, because the random bits ("coin flips") are visible to both machines. The IP approach is called a private coin protocol by contrast.

The essential problem with public coins is this: if the prover wishes to maliciously convince the verifier to accept a string which is not in the language, it seems like the verifier might be able to thwart its plans if it can hide its internal state from it. This was a primary motivation in defining the IP proof systems.

In 1986, Goldwasser and Sipser showed a surprising result: the verifier's ability to hide coin flips from the prover does it little good after all, in that an Arthur-Merlin public coin protocol with only two more rounds can recognize all the same languages. The result is that public-coin and private-coin protocols are roughly equivalent.³ In fact, as Babai shows in 1988, AM[k]=AM for all constant k, so the IP[k] have no advantage over AM.²

IP

Private coins may not be helpful, but more turns are: if we allow the probabilistic verifier machine and the all-powerful prover to interact for a polynomial number of rounds, we can solve the class of problems IP.

To demonstrate the power of the class IP, consider the graph isomorphism problem, the problem of determining whether it is possible to permute the vertices of one graph so that it is identical to another graph. This problem is in NP, since the proof certificate is the permutation which makes the graphs equal. Of course this problem is in IP, since NP is even contained in MA. Much more surprising was Adi Shamir's discovery of an IP algorithm to solve the complement of the isomorphism problem, a problem not known or believed to be in NP.⁴

Not only can such a machine solve many problems not believed to be in NP, but under practical assumptions about the existence of one-way functions, it is able to determine whether many problems have solutions without ever giving the verifier information about the solution. These are important when the verifier cannot be trusted with the full solution. At first it seems impossible that the verifier could be convinced that there is a solution when it has not seen it, but these so-called zero-knowledge proofs are in fact believed to exist for all problems in NP and are valuable in cryptography. Zero-knowledge proofs were invented in the original paper on IP by Goldwasser et al., but the extent of their power was shown by Oded Goldreich.

IP = PSPACE

So many problems seemed to topple before this powerful machine that an effort was made to establish just how much it could do. In 1992, Adi Shamir revealed in one of the central results of complexity theory that in fact, IP = PSPACE, the class of problems solvable by an ordinary deterministic Turing machine in polynomial space. This strong relationship between a probabilistic interactive protocol and a classical deterministic space-bounded machine gave a concept of the power and the limitations of interactive proof systems and established valuable ties between the two subfields.

Shamir's approach was to show that the quantified boolean formula problem, the canonical PSPACE-complete problem, has an IP protocol. He first uses a polynomial-time many-one reduction to put the formula in a special form where there is at most one universal quantifier between each variable's use and the quantifier binding it. He then derives an arithmetization of the formula, replacing or by addition, and by multiplication, not by subtraction from one, for all by a product over zero and one, and exists by a sum over zero and one. The resulting formula has a value, and this value is nonzero if and only if the original formula is true. But this value can potentially have an exponential number of bits, too large for the verifier; to deal with this, the prover chooses a prime p which has polynomial number of bits and all the computation is performed mod p. The prime p is chosen so that the result will remain nonzero if it was nonzero before.

The prover, having infinite power, can merely evaluate the new formula mod p, obtaining a single number. It gives this number to the verifier. The verifier's job is to prove that this number is probably correct. It does this by slowly picking apart the formula, at each point figuring out what the value of that part should be, and making sure that it is. More precisely, the verifier first evaluates any part of the formula which is not under a sum or product and subtracts or divides it out of the number. Then, the verifier removes the outermost sum or product. This "unbinds" one of the variables, turning the formula into a polynomial in that variable. But figuring out what this polynomial is could take exponential time, so the verifier asks the prover to do this for it. Once it receives the answer, the verifier can evaluate the original sum or product by plugging in both 0 and 1, then adding or multiplying the results. It then eliminates the free variable by substituting a random value less than p and proceeding. This whole process is repeated until all the sums or products are gone and the verifier can check the remainder by itself.

It's clear that if the prover is honest, giving an accurate original number and accurately finding the polynomials, this procedure is certain to succeed. But what if the formula is actually zero, but the prover wants to convince the verifier that it's nonzero? It would send some nonzero value initially, but then at each stage it would have to come up with polynomials that will produce the number the verifier is seeking. But then the interpolation theorem says that a polynomial of degree t can only agree with another polynomial for at most t input values. But t has a polynomial value, and p has a polynomial number of bits, which makes it exponentially larger. Each time that the verifier assigns a random value to one of the remaining variables, it becomes less and less likely that this value happened to be one of these few t values that the polynomials supplied by the prover will agree on. The result is that there is already exponentially small probability of false acceptance after a single run.

Now we know that PSPACE is contained in IP. The reverse containment is obvious: in polynomial space it's possible to consider every possible set of responses that the prover might make, and simulate the verifier's actions in response to them enough times to ensure very small error. The verifier will view any invalid responses as just being those of a dishonest prover.

Curiously, this theorem doesn't seem to use the "full power" of IP; if the input is in the language and the prover is honest it always accepts, not just with high probability. Likewise, it's not necessary to iterate it until the probability of false acceptance is exponentially small — it's already exponentially small. But since this protocol solves any problem in PSPACE = IP, this really says that these "extra" features are not actually needed in any interaction.

MIP

One goal of IP's designers was to create the most powerful possible interactive proof system, and at first it seems like it cannot be made more powerful without making the verifier more powerful and so impractical. Goldwasser et al. overcame this in their 1988 "Multi prover interactive proofs[...]", which defines a new version of IP called MIP in which there are two independent provers.⁷

The two provers cannot communicate once the verifier has begun sending messages to them. Just as it's easier to tell if a criminal is lying if he and his partner are interrogated in separate rooms, it's considerably easier to detect a malicious prover trying to trick the verifier into accepting a string not in the language if there is another prover it can double-check with.

In fact, this is so helpful that Babai, Fortnow, and Lund were able to show a result as astonishing as IP = PSPACE: that MIP = NEXPTIME, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. ⁸ This result would prove an inspiration to the designer of PCP, described next, who sought a "scaled-down" version that would relate an interactive proof system to NP.

MIP also has the helpful property that zero-knowledge proofs for every language in NP can be described without the assumption of one-way functions that IP must make. This has bearing on the design of provably unbreakable cryptographic algorithms.⁷ Moreover, a MIP protocol can recognize all languages in IP in only a constant number of rounds, and if a third prover is added, it can recognize all languages in NEXPTIME in a constant number of rounds, showing again its power over IP.

PCP

Main article: Probabilistically checkable proof

While the designers of IP considered generalizations of Babai's interactive proof systems, others considered restrictions. Perhaps the most useful of these was PCP(f(n), g(n)), which is a restriction of MA where Arthur can only use f(n) random bits and can only examine g(n) bits of the proof certificate sent by Merlin (essentially using random access). Designed by Sanjeev Arora and Shmuel Safra, the insight behind PCP is the idea that we can trade off full knowledge of the proof string for randomness without losing too much power.

There are a number of easy-to-prove results about various PCP classes. PCP(0,poly) (no randomness) is just NP, and PCP(poly,0) (no looking at the proof) is just co-RP. Arora and Safra's first major result was that PCP(log, log) = NP; put another way, if you take the verifier in the NP protocol and tell it it can only choose log n bits of the proof certificate to look at, this won't make any difference as long as you also give it log n random bits to use. ⁹

But there's more: although Arora and Safra knew they could not asymptotically lower both the number of random bits and the number of accesses, they believed they could lower one of them. Arora et al. eventually managed to show the PCP Theorem, another major complexity theory result asserting that the number of proof accesses could be brought all the way down to a constant. That is, NP = PCP(log, O(1)). ¹⁰ They used this valuable characterization of NP to prove that approximation algorithms do not exist for the optimization versions of certain NP-complete problems unless P = NP.

References

1. László Babai. Trading group theory for randomness (http://portal.acm.org/citation.cfm?id=22192). Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM. 1985.

2. László Babai and Shlomo Moran. Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes (http://portal.acm.org/citation.cfm?id=49987). Journal of Computer and System Sciences, 36: p.254-276. 1988.

3. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge complexity of interactive proof-systems (http://portal.acm.org/citation.cfm?id=63434). Proceedings of 17th Symposium on the Theory of Computation, Providence, Rhode Island. 1985. Extended abstract (http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf)

4. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems (http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc.pdf). Proceedings of ACM STOC'86, p.58-68. 1986.

5. O. Goldreich, S. Micali, A. Wigderson. Proofs that yield nothing but their validity (http://portal.acm.org/citation.cfm?id=116852). Journal of the ACM, volume 38, issue 3, p.690-728. July 1991.

6. Adi Shamir. IP = PSPACE (http://portal.acm.org/citation.cfm?doid=146585.146609). Journal of the ACM, volume 39, issue 4, p.869-877. October 1992.

7. M. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. Multi prover interactive proofs: How to remove intractability assumptions (http://theory.lcs.mit.edu/~cis/pubs/shafi/1988-stoc-bgkw.pdf). Proceedings of the 20th ACM Symposium on Theory of Computing, p.113-121. 1988.

8. László Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols (http://citeseer.ist.psu.edu/15039.html). Computational Complexity, volume 1, p.3-40. 1991.

9. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP (http://citeseer.ist.psu.edu/arora92probabilistic.html). Journal of the ACM, volume 45, issue 1, p.70-122. January 1998.

10. Sanjeev Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof Verification and the Hardness of Approximation Problems (http://citeseer.ist.psu.edu/376426.html). Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, p.13-22. 1992.

External links

Dexter Kozen. Interactive Proofs (http://www.cs.cornell.edu/Courses/cs682/2004sp/Lectures/l15-ip.pdf). CS682 Spring 2004 lecture notes. Department of Computer Science, Cornell University.
Complexity Zoo:
- MA (http://www.complexityzoo.com/#ma), MA' (http://www.complexityzoo.com/#maprime), MAEXP (http://www.complexityzoo.com/#maexp), MAE (http://www.complexityzoo.com/#mae)
- AM (http://www.complexityzoo.com/#am), AMEXP (http://www.complexityzoo.com/#amexp), AM intersect co-AM (http://www.complexityzoo.com/#amicoam), AM[polylog] (http://www.complexityzoo.com/#ampolylog), coAM (http://www.complexityzoo.com/#coam), BP•NP (http://www.complexityzoo.com/#bpnp)
- QMA (http://www.complexityzoo.com/#qma), QMA+ (http://www.complexityzoo.com/#qma+), QMA(2) (http://www.complexityzoo.com/#qma2), QMA_log (http://www.complexityzoo.com/#qmalog), QMAM (http://www.complexityzoo.com/#qmam)
- IP (http://www.complexityzoo.com/#ip), MIP (http://www.complexityzoo.com/#mip), IPP (http://www.complexityzoo.com/#ipp), QIP (http://www.complexityzoo.com/#qip), QIP(2) (http://www.complexityzoo.com/#qip2), compIP (http://www.complexityzoo.com/#compip), frIP (http://www.complexityzoo.com/#frip)
- PCP(r(n),q(n)) (http://www.complexityzoo.com/#pcp)