*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:

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

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:**= {<G,H>|G and H are isomorphic graphs}**

*ISO*
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:**= {<G,H>|G and H are**

*NOISO***isomorphic graphs}**

*not*
And the question is, using a classic proof, how can a prover convince a

*verifier*that two graphs are*isomorphic? We don't know how to provide short proofs that the graphs are not isomorphic and the***not***verifier*can't check every possibilities in polynomial time. Thus, we don't know how to prove that*is in***NOISO****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

**cannot be proved to the**

*NOISO**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

This is a really well-written blog. All new to me and made total sense. Nice work, Bin.

ReplyDeleteThe two are mixed up:

ReplyDelete- *Soundness*: any assertion with a proof is true

- *Completeness*: for any true assertion, there exists a proof

Fixing. Thanks for spotting.

Delete