Interactive proof system
Encyclopedia
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 and possesses unlimited computational resources, but cannot be trusted, 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:
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 describing interactive proof systems are AM and IP
.
may be viewed as a very simple proof system. In this system, the verifier is a deterministic, polynomial-time machine (a P
machine). The protocol is:
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.
, who published "Trading group theory for randomness", defined 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, it is more lenient:
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 considered as abstracting practical computation (see BPP).
, Silvio Micali
and Charles Rackoff
published 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 that 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, perhaps surprisingly, that 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.
To demonstrate the power of these classes, 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. It turns out that the
complement
of the graph isomorphism problem, a co-NP problem not known to be in NP, has an AM algorithm and the best way to see it is via a private coins algorithm.
In 1992, Adi Shamir
revealed in one of the central results of complexity theory that IP equals PSPACE
, the class of problems solvable by an ordinary deterministic Turing machine in polynomial space.
s, a prover can convince the verifier of the solution without ever giving the verifier information about the solution. This is 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 the verifier has not seen a certificate, but such proofs, known as zero-knowledge proof
s are in fact believed to exist for all problems in NP and are valuable in cryptography
. Zero-knowledge proofs were first mentioned in the original 1985 paper on IP by Goldwasser, Micali and Rackoff, but the extent of their power was shown by Oded Goldreich
, Silvio Micali
and Avi Wigderson
.
In fact, this is so helpful that Babai, Fortnow, and Lund were able to show that MIP = NEXPTIME
, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. NEXPTIME contains PSPACE, and is believed to strictly contain PSPACE. Adding a constant number of additional provers beyond two does not enable recognition of any more languages. This result paved the way for the celebrated PCP theorem
, which can be considered to be a "scaled-down" version of this theorem.
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.
).
There are a number of easy-to-prove results about various PCP classes. PCP(0,poly), the class of polynomial-time machines with no randomness but access to a certificate, is just NP. PCP(poly,0), the class of polynomial-time machines with access to polynomially many random bits is co-RP
. Arora and Safra's first major result was that PCP(log, log) = NP; put another way, if the verifier in the NP protocol is constrained to choose only O(log n) bits of the proof certificate to look at, this won't make any difference as long as it has O(log n) random bits to use.
Furthermore, the PCP theorem
asserts that the number of proof accesses can 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 algorithm
s do not exist for the optimization versions of certain NP-complete
problems unless P = NP. Such problems are now studied in the field known as hardness of approximation
.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, an interactive proof system is an abstract machine
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
that models computation
Computation
Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...
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
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
or not. The prover is all-powerful and possesses unlimited computational resources, but cannot be trusted, 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.
- SoundnessSoundness (Interactive proof)Soundness is a property of interactive proof systems that requires that no prover can make the verifier accept for a wrong statement y \not\in L except with some small probability...
: 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
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
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 describing interactive proof systems are AM and IP
IP (complexity)
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985...
.
NP
The complexity class NPNP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
may be viewed as a very simple proof system. In this system, the verifier is a deterministic, polynomial-time machine (a P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
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
Although NP may be viewed as using interaction, it wasn't until 1985 that the concept of computation through interaction was conceived by two independent groups of researchers. One approach, by László BabaiLászló Babai
László Babai is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields...
, who published "Trading group theory for randomness", defined the Arthur–Merlin (AM) class hierarchy. In this presentation, Arthur (the verifier) is a probabilistic
Probabilistic Turing machine
In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution....
, 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, it is more lenient:
- Completeness: 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).
- Soundness: 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 considered as abstracting practical computation (see BPP).
Public coins versus private coins
In the same conference where Babai defined his proof system for MA, Shafi GoldwasserShafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
, Silvio Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...
and Charles Rackoff
Charles Rackoff
Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, Rackoff attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar at INRIA in France.He currently works at the...
published 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 that 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
Michael Sipser
Michael Fredric Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. He received his Ph.D. in 1980 from the University of California, Berkeley under the direction of Manuel Blum....
showed, perhaps surprisingly, that 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.
To demonstrate the power of these classes, consider the graph isomorphism problem
Graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...
, 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. It turns out that the
complement
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement...
of the graph isomorphism problem, a co-NP problem not known to be in NP, has an AM algorithm and the best way to see it is via a private coins algorithm.
IP
Private coins may not be helpful, but more rounds of interaction are helpful. If we allow the probabilistic verifier machine and the all-powerful prover to interact for a polynomial number of rounds, we get the class of problems called IP.In 1992, Adi Shamir
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
revealed in one of the central results of complexity theory that IP equals PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
, the class of problems solvable by an ordinary deterministic Turing machine in polynomial space.
QIP
If we allow the elements of the system to use quantum computation, the system is called a quantum interactive proof system, and the corresponding complexity class is called QIP. A series of recent results culminating in a paper published in 2010 is believed to have demonstrated that QIP = PSPACE.Zero knowledge
Not only can interactive proof systems solve problems not believed to be in NP, but under assumptions about the existence of one-way functionOne-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
s, a prover can convince the verifier of the solution without ever giving the verifier information about the solution. This is 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 the verifier has not seen a certificate, but such proofs, known as zero-knowledge proof
Zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement....
s are in fact believed to exist for all problems in NP and are valuable in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. Zero-knowledge proofs were first mentioned in the original 1985 paper on IP by Goldwasser, Micali and Rackoff, but the extent of their power was shown by Oded Goldreich
Oded Goldreich
Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation...
, Silvio Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...
and Avi Wigderson
Avi Wigderson
Avi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...
.
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: How to remove intractability assumptions", which defines a variant 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 that MIP = NEXPTIME
NEXPTIME
In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O for some polynomial p, and unlimited space....
, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. NEXPTIME contains PSPACE, and is believed to strictly contain PSPACE. Adding a constant number of additional provers beyond two does not enable recognition of any more languages. This result paved the way for the celebrated PCP theorem
PCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...
, which can be considered to be a "scaled-down" version of this theorem.
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
While the designers of IP considered generalizations of Babai's interactive proof systems, others considered restrictions. A very useful interactive proof system is 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 accessRandom access
In computer science, random access is the ability to access an element at an arbitrary position in a sequence in equal time, independent of sequence size. The position is arbitrary in the sense that it is unpredictable, thus the use of the term "random" in "random access"...
).
There are a number of easy-to-prove results about various PCP classes. PCP(0,poly), the class of polynomial-time machines with no randomness but access to a certificate, is just NP. PCP(poly,0), the class of polynomial-time machines with access to polynomially many random bits is co-RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
. Arora and Safra's first major result was that PCP(log, log) = NP; put another way, if the verifier in the NP protocol is constrained to choose only O(log n) bits of the proof certificate to look at, this won't make any difference as long as it has O(log n) random bits to use.
Furthermore, the PCP theorem
PCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...
asserts that the number of proof accesses can 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 algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
s do not exist for the optimization versions of certain NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems unless P = NP. Such problems are now studied in the field known as hardness of approximation
Hardness of approximation
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. It complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can...
.
Textbooks
- Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach", Cambridge University Press, March 2009. Section 10.4: Interactive Proof Systems, pp. 354–366. Section 19.2: Games against nature and interactive protocols, pp. 469–480.
External links
- Dexter Kozen. Interactive Proofs. CS682 Spring 2004 lecture notes. Department of Computer Science, Cornell University.
- Complexity Zoo:
- Larry Gonick. "Proof Positive?". A comic strip about interactive proof systems.