52 Things: Number 8: How does interaction help in computation, and what is the class IP?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This blog post concentrates on the power of interaction in computation and the Complexity Class IP.

To answer the questions, we first give give a brief introduction of the interactive proof systems. As we know, zero-knowledge proofs currently play an important role in the study of cryptographic protocols. This concept was introduced by Goldwasser, Micali and Rackoff in [1]. Such proofs have the fascinating property of revealing nothing other than the validity of assertions being proven. In order to achieve this, Goldwasser, Micali and Rackoff developed the interactive proof systems by adding two ingredients to the classical proof systems. The first ingredient is randomisation, the verification of proofs can be probabilistic and the verifier is allowed to err with small probability. The second one is interaction, the static proof is replaced by dynamic prover who will interact with the verifier to convince it the assertion is true. Combining the classical proof systems with the two ingredients has a huge effect: the set of languages of interactive proof systems is in a large complexity class IP. 

What is a proof?

Loosely speaking, a proof is a way for a party to convince another party that a certain assertion is true. The two parties involved in a proof system are called a prover and a verifier.

Classical proofs

A classical mathematical proof is a fixed sequence of statements, which can be all written down by the prover then the verifier can easily check the validity of the assertion. There is no interaction between the prover and the verifier. 

Any proof system should have the following properties: 

1. Efficiency: the verification procedure can be carried out efficiently. 
2. Soundness: for any false assertion, invalid proofs are hard to find. 
3. Completeness: for any true assertion, there exists a proof. 

Recall the complexity class NP can be viewed as a class of languages whose members all have certificates that can be easily checked (the non-members do not have certificates). Hence we have NP is exactly the class of languages of classical proofs. 

Interactive Proofs

In an interactive proof system, the prover and verifier are allowed to interact with each other by exchange of messages. Before introducing the concept of interactive proofs, we first give an example (which can be found in [2]) to show how does interaction help in computation. 

Example: Graph Isomorphism and Graph Non-isomorphism.

Two graphs G and H are called isomorphic if the nodes of G can be reordered so that it is identical to H. We define the language:

ISO = {<G,H>|G and H are isomorphic graphs}

It is clear that ISO is in NP. Even though the number of nodes can be very large, the membership of ISO can be easily verified by given the instructions of reordering.

Then we consider the complement problem of Graph Isomorphism, namely Graph Non-isomorphism. We define the language:

NOISO = {<G,H>|G and H are not isomorphic graphs}

And the question is, using a classic proof, how can a prover convince a verifier that two graphs are not isomorphic? We don't know how to provide short proofs that the graphs are not isomorphic and the verifier can't check every possibilities in polynomial time. Thus, we don't know how to prove that NOISO is in NP. Nevertheless, consider the following interactive protocol, the prover can convince the verifier the fact that the given two graphs are not isomorphic. 

Both the prover and the verifier have a pair of graphs $(G_1, G_2)$ as common input. The verifier randomly choose a random bit $b \in \{0,1\}$ and a permutation $\pi$. Then it applies $\pi$ on $G_b$ to get a graph $H$. The verifier sends $H$ to the prover. Next, upon received $H$, the prover sends $b' \in \{0,1\}$ to the verifier. Finally, the verifier accepts if and only if $b'=b$. 

The idea behind the protocol is, if the given graphs $(G_1,G_2)$ are not isomorphic, then the prover should be able to identify $H$ is from either $G_1$ or $G_2$. However, if the input graphs are isomorphic, even with unlimited computational power, the best choice of the prover is to make $b'$ a random guess. In this case, the prover accepts at most $\frac{1}{2}$.

From the above example, we conclude that NOISO cannot be proved to the verifier via a classic proof, whereas it could be proved via an interactive proof(protocol). We can see there is some power in interaction. 

Now we give the formal definition of interactive proofs and the complexity class IP. 

Interactive proof system: A pair of interactive machines $(P,V)$ is called an interactive proof system for a language L if machine V is polynomial-time and the following conditions hold:

• Completeness: For ever $x \in L$,

$Pr[<P,V>(x)=1] \geq \frac{2}{3}$

• Soundness: For every $x \notin L$

$Pr[<P,V>(x)=1] \leq \frac{1}{3}$

The class IP: The class IP consists of all languages having interactive proof systems. 

By the definition, it is obvious that any language in BPP is in IP. And if we restrict the exchange of messages between the machines to be $1$, then we have NP is in IP. Actually, IP is a surprisingly large class. In 1992, Shamir revealed that PSPACE=IP [3]. 

In addition, notice that in the protocol, the prover has the ability to toss a private-coin. If the prover is allowed to access to the verifier's random string leads to the model of interactive proofs with public-coins, which is related to a similar complexity class AM [4]. 

[1] http://dl.acm.org/citation.cfm?id=63434

[2] http://www.amazon.co.uk/Introduction-Theory-Computation-Michael-Sipser/dp/0619217642

[3] http://dl.acm.org/citation.cfm?doid=146585.146609

[4] http://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol