Interactive Proof Systems
Abstract
The concept of a "proof" is hard to define formally. Usually we have an intuitive notion about how to convince a human being that a particular Theorem one made up is true. There are two different concepts how this convincing work can be done. The first is to write down the proof. Then the person to be convinced reads it and tries to put the writer’s thoughts together. The second concept allows communication between the prover and the verifier of the proof. In a lecture, for example, students (the verifiers) and the teacher (the prover) interact. Interactive Proof Systems utilize this concept of interaction in a formal way. They represent a computation model that consists of more than one computing entity. It is interesting to examine how big the problem class is, that can be dealt with, if we pose certain restrictions on our abstract computing devices.
Complexity Classes
The terms deterministic/nondeterministic Turing machine are used here in the usual way. They are defined precisely in Papadimitriou, 1994, for example. Turing machines can accept or decide languages.
If a language L is decided by some Turing machine, L is called a recursive language.
If a language L is accepted by some Turing machine, L is called a recursively enumerable language.
Definition of DTIME(f), NTIME(f), DSPACE(f), NSPACE(f):
DTIME(f) is the complexity class that consists of all languages that are decided by some deterministic Turing machine M, such that for any input x, M spends at most f(|x|) units of time.
NTIME(f) is the complexity class that consists of all languages that are decided by some nondeterministic Turing machine M, such that for any input x, M spends at most f(|x|) units of time.
DSPACE(f) is the complexity class that consists of all languages that are decided by some deterministic Turing machine M, such that for any input x, M spends at most f(|x|) units of space.
NSPACE(f) is the complexity class that consists of all languages that are decided by some nondeterministic Turing machine M, such that for any input x, M spends at most f(|x|) units of space.
Definition of major complexity classes:
P:=È j>0 DTIME(nj)
NP:=È j>0 NTIME(nj)
PSPACE:=È j>0 DSPACE(nj)
NPSPACE:=È j>0 NSPACE(nj)
L:=DSPACE(log n)
NL:=NSPACE(log n)
EXP:=È j>0 DTIME(2n^k)
NEXP:=È j>0 NTIME(2n^k)
EXPSPACE:=È j>0 DSPACE(2n^k)
R:= the recursive languages
RE:= the recursively enumerable languages
The hierarchy of the traditional major complexity classes is as follows: (Í denotes that it is not known if the inclusion is proper, Ì denotes a proper inclusion)
L Í NL Í P Í NP Í PSPACE = NPSPACE Í EXP Í NEXP Í EXPSPACE Ì R Ì RE
P Í coNP Í PSPACE
P Ì EXP
L Ì PSPACE
History of Interactive Proof Systems
Interactive proof systems have been introduced by Goldwasser/Micali/Rackoff, 1985. Their goal was to measure the amount of knowledge needed to communicate a proof. This was the source of a mathematical theory about cryptographic protocols.
Independent of that Babai, 1985, developed the concept of Arthur-Merlin systems. They can be seen as a special case of interactive proof systems. Their first purpose was to provide efficient computations in groups constructed by generator lists.
Descriptions of different kinds of Interactive Proof Systems
An Interactive Proof System consists of two Turing machines (P) and (V) and a set of tapes that allows communication between them. P (the prover) is a computationally unlimited Turing machine; V (the verifier) is a deterministic Turing machine with a polynomial time limit (polynomial with respect to the length of the input). Let w be an input string of length n. It is fed into the system on an input tape, which is readable by both P and V. P and V take turns to be active. Every time one of them is active it can read data from designated tapes, it can write data to a designated tape and it can change its internal state. Communication between P and V takes place via writing and reading to those communication tapes. The acceptance criterion is defined through the final states of V. When V has stopped its computation (i.e. no more V-movements are carried out) the input string is accepted or rejected. Since V has a polynomial time limit, the length of the messages is polynomially bounded. In addition to that, it is assumed that the number of message exchanges (called rounds) is also polynomially bounded.
Deterministic Interactive Proof Systems (DIP)
If no additional features are added, this model defines the complexity class DIP (Deterministic Interactive Proof system) which has been shown to be equivalent to NP (e.g. Bovet/Crescenzi, 1994).
Interactive Proof Systems (IP)
If a random device is introduced into the model as follows, then the complexity class IP (Interactive Proof system) is defined. Shamir, 1990, showed in a very elegant proof that IP is equivalent to PSPACE. The difference between a deterministic interactive proof system (DIP) and an interactive proof system (IP) is that the verifier V in IP is now a probabilistic Turing machine with a polynomial time bound. This means V also reads random data r from a tape that is only accessible to V, but not to P. An equivalent design uses a private random number generator that produces "private coins" for P.
Those changes also require change of the acceptance criterion. The language L is said to be accepted by V, if for all x in L the probability that V accepts x is greater or equal than 2/3 and for all x not in L the probability that V accepts x is less than or equal to 1/3. (It can be shown that the above bounds can be chosen from the interval ]1/2; 1[ and ]0; 1/2[, respectively, without having any effect on the resulting complexity class IP.
Arthur-Merlin System (AM)
If the only messages that V sends to P consist of chunks of the random string r, i.e. the random string r is passed on to P one character per round of communication, the interactive proof system is called an Arthur-Merlin system and the corresponding complexity class is named AM[poly]. An alternative design would be to introduce a public number generator that supplies both P and V with random numbers, one at a time. Goldwasser/Sipser, 1986, showed that the power of interactive proof systems and Arthur-Merlin systems is the same, i.e. IP=AM[poly].
Nevertheless it is useful to be familiar with both IP systems and AM systems. It is easier to develop protocols for IP systems, whereas proving structural complexity results is easier with AM systems. Using the fact that IP=AM[poly] therefore often provides a useful shortcut.
Examples
The way DIP and IP were defined, it is obvious that DIPÍ IP, since any IP system can simulate a DIP system by just ignoring the random string. The question, if the above inclusion is proper, can be answered by examining the following example.
The Problem Graphnonisomorphism (GNI)
Two graphs G1(N1,V1) and G2(N2,V2) are called isomorphic, if there is a bijection f: N1® N2, such that for all x,y Î N1 the following is valid: (x,y) Î E1 if and only if (f(x),f(y)) Î E2.
If no such bijection exists, G1 and G2 are nonisomorphic.
The language Graphisomorphism (GI) consists of all pairs of graphs having the same nodes and being isomorphic to each other.
The language Graphnonisomorphism (GNI) consists of all pairs of graphs having the same nodes and being nonisomorphic to each other.
It is not hard to see that GI is in NP. A nondeterministic Turing machine can guess a bijection f and verify in polynomial time that the two input graphs are isomorphic. On the other hand it is not known at this time, if GNI is in NP. (GNI is in co-NP, since GI and GNI are complementary problems). It is conjectured that GNI is not in NP.
For the purpose of illustration here is an IP system that accepts GI (from Koebler/Scoening/Toran, 1993):
Let the pair of Graphs (G1,G2) be on the input tape. The prover P starts by using his unlimited computational power to compute an isomorphism between G1 and G2, if one exists, and sends it to the verifier V via the communication tape. V reads the proposed isomorphism and checks that it is indeed an isomorphism. This can be done in polynomial time. V accepts if it got an isomorphism, otherwise V rejects.
With this protocol V will accept with probability 1, if G1 and G2 are isomorphic and V will reject with probability 1, if G1 and G2 are nonisomorphic, since no prover whatsoever will be able to send V an isomorphism. Therefore GI is in IP.
In the following example we come up with an IP system that accepts GNI. So GNI is in IP, but probably not in NP, and therefore probably IP!=NP. This also implies that GNI is probably harder than GI.
The following protocol sets up an IP system that accepts GNI:
Let the pair of Graphs (G1,G2) be on the input tape.
The verifier V then starts by guessing a number i Î {1,2} and by guessing a random permutation of the vertices. V can do so because of its probabilistic feature. V then computes the graph H that is the result of applying the random permutation to the graph Gi. Then V sends H to P via the communication tape.
The prover P then computes, if H is isomorphic to G1. If so, he responds to V by sending the value 1, otherwise he sends the value 2.
Finally V rejects if P's response does not match his random i. V accepts if P's response matches his i two times.
How powerful is IP?
Shamir, 1990, showed in a very elegant and compact proof that IP=PSPACE.
The inclusion IPÍ PSPACE has been established quite a while before. Sipser, 1997, contains a proof of it. He constructs a polynomial space bounded Turing machine M that simulates an IP system for the prover with the maximal probability of acceptance. In order to determine if a word w is in the language L or not, one must calculate the probability with which V accepts w in polynomial space.
In order to show the other inclusion PSPACEÍ IP it is sufficient to prove that a PSPACE-complete problem is in IP. This is because the complexity class IP is closed from below under polynomial time reductions. The PSPACE-complete problem Shamir used in his proof is a variant of the problem QBF (quantified boolean formulas). Certain QBFs can be transformed to arithmetic expressions that have the nice property that they are short and easy to evaluate. To achieve the required efficiency calculations are performed in the finite field modulo p, where p is an appropriate prime number. The existence of such a prime p can be guaranteed referring to the prime number theorem. Mauch, 1998, used the much weaker Chebyshev's inequality for prime numbers to ensure that such a prime exists. The final step of the proof is coming up with an interactive protocol for an IP system that decides the variant of QBF.
Summary
The hierarchy of all the complexity classes mentioned in this paper is as follows: (Í denotes that it is not known if the inclusion is proper, Ì denotes a proper inclusion)
L Í NL Í P Í NP = DIP Í PSPACE = IP = AM[poly] = NPSPACE Í EXP Í NEXP
Í EXPSPACE Ì R Ì RE
P Í coNP Í PSPACE
P Ì EXP
L Ì PSPACE
References