Interactive Proof Systems

The Verifier and the Prover

Interactive proof systems provide a probabilistic analog of the class $\mathrm{NP}$, similar to how probabilistic polynomial time algorithms provide an analog to $\mathrm{P}$

These have important implications to cryptography and approximation algorithms

Recall that the languages in $\mathrm{NP}$ are those whose members all have easily verifiable certificates of membership

We reformulate this concept as a Prover with unlimited time and a Verifier with polynomially bounded time

Informally, an interactive proof system takes this formulation, allows for two-way dialog, and lets the Verifier be a probabilistic polynomial time machine

This kind of system can decide problems such as the complement of $SAT$ (within the degree of accuracy we specify)

Example:
$ISO=\{⟨G,H⟩\mid G\text{ and }H\text{ are isomorphic graphs}\}$ is in $\mathrm{NP}$, but is neither proven to be in $\text{P}$ or $\mathrm{NP}$-complete

The complementary language $NONISO$ is not even known to be in $\mathrm{NP}$

However our setup enables a Prover to convince a Verifier that two graphs aren’t isomorphic with a very simple scheme

The Verifier randomly selects either $G_1$ or $G_2$, randomly reorders its nodes to produce $H$, and asks the Prover whether $G_1$ or $G_2$ is the source of $H$

With unlimited computational power, the Prover can consistently answer correctly only if the graphs are nonisomorphic

Therefore, if the Prover answers correctly over many trials, the Verifier has convincing evidence that the graphs are nonisomorphic

Definition:

• The Verifier is a function $V(w,r,m_1\#\dots \#m_i)=m_{i+1}$ that computes its next transmission (or accept/reject) from the input string, a random string (for convenience), and the message history
• The Prover is a function $P(w,m_1\#\dots \#m_i)=m_{i+1}$ that computes is next transmission from the input string and the message history
• We write the interaction between the Prover and the Verifier as $V\leftrightarrow P$ and write $(V\leftrightarrow P)(w,r)=accept$ if a message sequence $m_1,\dots ,m_k$ exists such that $V(w,r,m_1\#\dots \#m_i)=m_{i+1}$ for even $i$, $P(w,m_1\#\dots \#m_i)=m_{i+1}$ for odd $i$, and $m_k=accept$

$\mathrm{Pr}[V\leftrightarrow P\text{ accepts }w]=\mathrm{Pr}[(V\leftrightarrow P)(w,r)=accept]$

We also assume the lengths of the Verifier’s random input, the lengths of the messages exchanged, and the total number of messages is at most $p(n)$ for some polynomial $p$ that depends only on the Verifier

Definition: $A\in \mathbf{IP}$ if some polynomial time computable function $V$ exists such that for some function $P$ and for every function $\tilde{P}$, for every string $w$, $w\in A⟹\mathrm{Pr}[V\leftrightarrow P\text{ accepts }w]\ge \frac{2}{3}$ and $w\notin A⟹\mathrm{Pr}[V\leftrightarrow \tilde{P}\text{ accepts }w]\le \frac{1}{3}$

The second clause guarantees the Verifier has true evidence of $w\in A$ and can’t rely on the power of the Prover

Note that the specific constants chosen in this definition are arbitrary (and we may amplify the probability by repetition)

$\mathrm{IP}$ is clearly more powerful than both $\mathrm{NP}$ and $\mathrm{BPP}$, and indeed contains $NONISO$, which is not known to be in either

IP = PSPACE

$\mathrm{IP}$ is remarkably powerful, and in fact is proven to be equal in power to $\mathrm{PSPACE}$

Theorem: $\mathrm{IP}=\mathrm{PSPACE}$

We divide this into two parts

IP ⊆ PSPACE

Let $A$ be a language in $\mathrm{IP}$, with Verifier $V$ that exchanges $p=p(n)$ messages on input $w$ with length $n$

We construct a $\mathrm{PSPACE}$ machine that simulates $V$, calculating the probability for any string $w$, $\mathrm{Pr}[V\text{ accepts }w]={\max }_P\mathrm{Pr}[V\leftrightarrow P\text{ accepts }w]$

Let $M_j$ denote the message history $m_1\#\dots \#m_j$

We write $(V\leftrightarrow P)(w,r,M_j)=accept$ if we can extend $M_j$ with messages that lead to an accept (maintaining that any messages before $M_j$ are consistent)

We write ${\mathrm{Pr}}_r$ to consider taking the probability over all strings $r$ consistent with $M_j$,
$\mathrm{Pr}[V\leftrightarrow P\text{ accepts }w\text{ starting at }{M}_j]={\mathrm{Pr}}_r[(V\leftrightarrow P)(w,r,M_j)=accept]$
$\mathrm{Pr}[V\text{ accepts }w\text{ starting at }{M}_j]={\max }_P\mathrm{Pr}[V\leftrightarrow P\text{ accepts }w\text{ starting at }{M}_j]$

We define our final probability inductively, going from $j=p$ to 0

$N_{M_p}=1$ if $M_p$ is consistent and 0 otherwise
For $j<p$, $N_{M_j}=\{\begin{array}{ll}{\max }_{m_{j+1}}{N}_{M_{j+1}}& \mathrm{odd}j<p\\ {\text{wt-avg}}_{m_{j+1}}{N}_{M_{j+1}}& \mathrm{even}j<p\end{array}$

We define ${\text{wt-avg}}_{m_{j+1}}{N}_{M_{j+1}}={\sum }_{m_{j+1}}^{}(\mathrm{Pr}[V(w,r,M_j)=m_{j+1}]\cdot N_{M_{j+1}})$

First, note that we can calculate $N_{M_0}$ in polynomial space, by recursively calculating $N_{M_j}$ for every $j$ and $M_j$, since our messages take polynomial space

Second, $N_{M_0}=\mathrm{Pr}[V\text{ accepts }w]$ is our target value

To show this is true, we inductively prove $N_{M_j}=\mathrm{Pr}[V\text{ accepts }w\text{ starting at }{M}_j]$

The base case $j=p$ is trivial

Assuming our claim holds for $j+1\le p$ and any message stream $M_{j+1}$, we prove it is true for $j$ and any $M_j$

If $j$ is even, $m_{j+1}$ is a message from $V$ to $P$,
$N_{M_j}={\sum }_{m_{j+1}}^{}({\mathrm{Pr}}_r[V(w,r,M_j)=m_{j+1}]\cdot N_{M_{j+1}})$
$={\sum }_{m_{j+1}}^{}({\mathrm{Pr}}_r[V(w,r,M_j)=m_{j+1}]\cdot \mathrm{Pr}[V\text{ accepts }w\text{ starting at }{M}_{j+1}])$
$=\mathrm{Pr}[V\text{ accepts }w\text{ starting at }{M}_j]$

If $j$ is odd, $m_{j+1}$ is a message from $P$ to $V$,
$N_{M_j}={\max }_{m_{j+1}}{N}_{M_{j+1}}={\max }_{m_{j+1}}\mathrm{Pr}[V\text{ accepts }w\text{ starting at }{M}_{j+1}]$
$=\mathrm{Pr}[V\text{ accepts }w\text{ starting at }{M}_j]$

This last equality holds because we are looking at probabilities maximizing over all possible Provers

The Counting Problem

Before showing the proof for $\mathrm{PSPACE}\subseteq \mathrm{IP}$, we begin with a weaker result that illustrates the technique

The counting problem for satisfiability $\#SAT$ identifies whether $\varphi$ is a cnf-formula with exactly $k$ satisfying assignments

Theorem: $\#SAT\in \mathrm{IP}$

Arithmetization associates $\varphi$ with a polynomial $p(x_1,\dots ,x_m)$, where $p$ is designed to mimic $\varphi$ on Boolean assignments

• $\alpha \wedge \beta ⟹\alpha \beta$
• $\neg \alpha ⟹1-\alpha$
• $\alpha \vee \beta ⟹\alpha \ast \beta =1-(1-\alpha )(1-\beta )$

The degree of any variable is at most $n$, the length of $\varphi$

It’s not clear how we’d interpret assigning non-Boolean values, however this proof does just this, exactly as was done here to prove $E{Q}_{\mathrm{ROBP}}\in \mathrm{BPP}$

This technique is powerful because while two different formulas can agree on many points, two different polynomials with limited degree can only agree on a small set of points

This idea is more clear when we write out and verify the protocol

We look at a finite field $\mathcal{F}$ with $q>2^n$ elements

Let $f_i(a_1,\dots ,a_i)={\sum }_{a_{i+1},\dots ,a_m}^{}p(a_1,\dots ,a_m)$ be the number of valid assignments with $a_1,\dots ,a_i\in \mathcal{F}$ fixed and $a_{i+1},\dots ,a_m\in \{0,1\}$

$f_0()$ is the number of satisfying assignments of $\varphi$, and each $f_i(x_1,\dots ,x_i)$ can be expressed as a polynomial in $x_1$ through $x_i$, with degrees at most that of $p$

In Phase 0: $P$ sends $f_0()$ to $V$, and $V$ rejects if $k\ne f_0()$

In Phase 1: $P$ sends the coefficients of $f_1(z)$ as a polynomial in $z$, and $V$ rejects if $f_0()\ne f_1(0)+f_1(1)$
$V$ sends over a random $r_1$ from $\mathcal{F}$

In Phase 2: $P$ sends the coefficients of $f_2(r_1,z)$ as a polynomial in $z$, and $V$ rejects if $f_1(r_1)\ne f_2(r_1,0)+f_2(r_1,1)$
$V$ sends over a random $r_2$ from $\mathcal{F}$

This continues until $P$ reaches the end and may directly check that $p(r_1,\dots ,r_m)=f_m(r_1,\dots ,r_m)$, in which case $V$ accepts

If $\varphi$ does have $k$ satisfying assignments, then $V$ clearly accepts

The tricky part is understanding why $\tilde{P}$ (a crooked Prover) cannot deceive $V$ if $\varphi$ doesn’t have $k$ assignments

To prevent $V$ from rejecting outright, $\tilde{P}$ sends an incorrect ${\tilde{f}}_0()$

This lie immediately propagates, since one of the values $V$ calculates for $f_1(0)$ and $f_1(1)$ must be incorrect if $V$ is not to reject, so $\tilde{P}$ must send an incorrect ${\tilde{f}}_1(z)$

The key in our construction is showing that the lie must continue to propagate, i.e. ${\tilde{f}}_1(r_1)$ is unlikely to equal $f_1(r_1)$

Using this result, the probability that they happen to agree is $\le n/2^n<n^{-2}$ (for $n\ge 10$)

In the general case, this means that if ${\tilde{f}}_{i-1}(r_1,\dots ,r_{i-1})\ne f_{i-1}(r_1,\dots ,r_{i-1})$, then for $n\ge 10$ and for $r_i$ chosen at random in $\mathcal{F}$, $\mathrm{Pr}[{\tilde{f}}_i(r_1,\dots ,r_i)=f_i(r_1,\dots ,r_i)]\le n^{-2}$

The probability that $\tilde{P}$ gets lucky at some point is at most the number of phases $m$ times $n^{-2}$, or at most $1/n$

Otherwise, $V$ will catch the incorrect value of $f_m$ by calculating it directly in Phase $m+1$

PSPACE ⊆ IP

We can show this by proving that $TQBF$ is in $\mathrm{IP}$

Let’s start by following the same reasoning as in our proof above

Let $\psi$ be a quantified Boolean formula of the form $\psi =Q_1{x}_1{Q}_2{x}_2\dots Q_m{x}_m[\varphi ]$

Again, we define $f_i(a_1,\dots ,a_i)=\{\begin{array}{ll}1& \text{if }{Q}_{i+1}{x}_{i+1}\dots Q_m{x}_m[\varphi (a_1,\dots ,a_i)]\\ 0& \mathrm{otherwise}\end{array}$

By this definition, $f_0()$ is our final truth value

Our quantifiers give us two new arithmetic identities,
$Q_{i+1}=\forall$: $f_i(a_1,\dots ,a_i)=f_{i+1}(a_1,\dots ,a_i,0)\cdot f_{i+1}(a_1,\dots ,a_i,1)$
$Q_{i+1}=\exists$: $f_i(a_1,\dots ,a_i)=f_{i+1}(a_1,\dots ,a_i,0)\ast f_{i+1}(a_1,\dots ,a_i,1)$ (recall $x\ast y=1-(1-x)(1-y)$)

We run into an issue if we proceed as before, because these identifiers are effectively doubling the degree of the resulting polynomial each time, leading to an exponential number of coefficients

To fix this, we include a new operator to help reduce the degree of our polynomials,
${\psi }^{\prime }=Q{x}_{1}R{x}_{1}Q{x}_{2}R{x}_{1}R{x}_{2}Q{x}_{3}R{x}_{1}R{x}_{2}R{x}_3\dots Q{x}_{m}R{x}_1\dots R{x}_m[\varphi ]$

We simplify as ${\psi }^{\prime }=S_1{y}_1{S}_2{y}_2\dots S_k{y}_k[\varphi ]$ where $S_i\in \{\forall ,\exists ,R\}$ and $y_i\in \{x_1,\dots ,x_m\}$

For each $i\le k$, we define $f_i$

$f_k(x_1,\dots ,x_m)$ is the polynomial $p(x_1,\dots ,x_m)$ obtained by arithmetizing $\varphi$

For $i<k$,
$S_{i+1}=\forall$: $f_i(\dots )=f_{i+1}(\dots ,0)\cdot f_{i+1}(\dots ,1)$
$S_{i+1}=\exists$: $f_i(\dots )=f_{i+1}(\dots ,0)\ast f_{i+1}(\dots ,1)$
$S_{i+1}=R$: $f_i(\dots ,a)=(1-a)f_{i+1}(\dots ,0)+a{f}_{i+1}(\dots ,1)$

While $f_i$ has one fewer input variable than $f_{i+1}$ for $\forall$ and $\exists$, this is not the case for $R$, so $f_i$ does not generally depend on $i$ variables

In addition, we reorder the inputs to the functions so that input variable $y_{i+1}$ is the last argument, such that $S_{i+1}=R$ has the effect of producing a result linear in $y_{i+1}$ but with the same truth value

This way, each degree is reset to 1 prior to squaring due to quantifiers

We choose a field $\mathcal{F}$ of size at least $n^4$, where $n$ is the length of $\varphi$

In Phase 0: $P$ sends $f_0()$ to $V$, and $V$ rejects if $f_0()\ne 1$

In Phase $i$: $P$ sends the coefficients of $f_i(r_1\dots ,z)$ as a polynomial in $z$
$V$ evaluates $f_i(r_1\dots ,0)$ and $f_i(r_1\dots ,1)$

$V$ checks that $f_{i-1}(r_1\dots )=\{\begin{array}{ll}{f}_i(r_1\dots ,0)\cdot f_i(r_1\dots ,1)& S_i=\forall \\ f_i(r_1\dots ,0)\ast f_i(r_1\dots ,1)& S_i=\exists \end{array}$
Or if $S_i=R$ then $f_{i-1}(r_1\dots ,r)=(1-r)f_i(r_1\dots ,0)+r{f}_i(r_1\dots ,1)$
If this fails then $V$ rejects

$V$ picks a random $r$ in $\mathcal{F}$ and sends it to $P$, continuing the protocol

In Phase $k+1$: $V$ directly checks that $p(r_1,\dots ,r_m)=f_k(r_1,\dots ,r_m)$, accepts if so and rejects otherwise

The correctness of this protocol follows similar to the $\#SAT$ protocol

Clearly if $\psi$ is true then $P$ can follow the protocol and $V$ will accept
If $\psi$ is false, $\tilde{P}$ must send a lie for $f_0()$

At Phase $i$, if $V$ has an incorrect value for $f_{i-1}(r_1\dots )$ then the polynomial for $f_i$ must also be incorrect

Then, the chance that $f_i(r_1\dots ,r)$ happens to be the correct value is at most the polynomial degree divided by the field size $n/n^4$

The protocol proceeds for $O(n^2)$ phases, so the probability that $\tilde{P}$ gets lucky at some point is at most $1/n$

Otherwise, $V$ will catch the incorrect value of $f_k$ by calculating it directly in Phase $k+1$