Probabilistically Checkable and Interactive Proof Note 1

Posted on In Disqus:

All info comes from Alessandro Chiesa’s Lecture CS294 2019 version.

We are now trying to figure out relation $\text{IP = PSPACE}$.

$\text{IP}\subseteq\text{PSPACE}$

Let $L \in \text{IP}$, we have interactive proof verifier $V_L$. Fix an instance $x$ to have $q_x \triangleq \max\limits_{\overset{\sim}{P}}\Pr\left[\langle \overset{\sim}{P},V_L\rangle (x) \right]$. $q_x$ has properties that $\begin{cases} x\in L&\to q_x = 1\newline x\notin L &\to q_x \le \dfrac{1}{2}\end{cases}$.

If we can compute $q_x$ in $\text{PSPACE}$, then $L$ is also in $\text{PSPACE}$.

Define transcript $\text{tr} = (p_1,v_1,\dots,p_i,v_i)$.

Define $\text{P}^\ast(x, \text{tr})$ to be a function that outputs $p_{i+1}$ that maximize $\Pr\left[ V_L = 1\right]$ based on $\text{tr}$.

If $P^\ast \in \text{PSPACE}$, then $q_x \in \text{PSPACE}$

For every random string $\mathbf{r}$ of $V_L$, compute the bit $b = b(x,\mathbf{r}) = V_L(x,\mathbf{r},p_1^\ast,\dots,p_l^\ast)$, where
$$
\begin{aligned}
p_1^\ast &= P^\ast(x,\bot)\newline
v_1 &= V_L(x,\mathbf{r}, p_1^\ast)\newline
p_2^\ast &= P^\ast(x, \text{tr} = (p_1^\ast, v_1))\newline
v_2 &= V_L(x,\mathbf{r}, p_1^\ast,p_2^\ast)\newline
&\dots
\end{aligned}
$$
Compute $q_x = \dfrac{\sum\limits_{\mathbf{r}\in R} b(x, \mathbf{r})}{|R|}$. Noticing we play $|R|$ times of game of interactive proof with different $\mathbf{r}$ on function $b$, where $P^\ast$ is asserted as $\text{PSPACE}$ and $V_L$ is $\text{poly}$, so $q_x$ is $\text{PSPACE}$ if $|R|$ is constant.

$P^\ast \in \text{PSPACE}$

Let $\mathcal{C}(x, \text{tr}) \subseteq R$ be the set of strings $\mathbf{r}$ that are consistent with $(x, \text{tr})$ that, namely, if $\text{tr} = (p_1,v_1,\dots,p_i,v_i)$, then $v_i = V_L(x,\mathbf{r}, p_1,\dots, p_i)$.

$P^\ast$ is defined recursively that $P^\ast(x, (p_1,v_1,\dots,p_{l-1},v_{l-1})) \to p^\ast_{l} = \arg\max\limits_{p_l} \mathbb{E}(\underset{\mathbf{r}\leftarrow \mathcal{C}(x,\text{tr})}{V_L}(x, \mathbf{r}, p_1,\dots,p_{l-1}))$.

The prover can choose $p_l$ from possible $p_l$ space and do the $V_L$ testing. Each $p_l$ keep track of the expectation and roll back the memory. Keep track of the best $p_l$ and return.

All we want is pick the best $p_l$ and keep a polynomial space complexity.

Sumcheck Protocol and IP for Counting Problems

Given a boolean function $\phi$ with $n$ variables and $m$ clauses, there are $2^n$ possible assignments out there.

Considering a $\text{UN-SAT}$ problem, we want to prove that $\not\exists \lbrace a_i\rbrace$ that $\phi(a_1,\dots,a_n) = 1$ and we want to convince $V$ with a $\text{poly}(m, n)$ resource.

We can translate the problem from logic side to algebraic side by mapping the logical formula $\phi$ to a low degree polynomial $P$.
$$
3 \text{-CNF } \phi\ (n\text{ vars}, m\text{ clauses}) \mapsto \text{low-degree polynomial }P(x_1, \dots, x_n)
$$

E.g.
$$
\begin{aligned}
&(x_1 \vee x_2 \vee x_3) \wedge (x_4 \vee \overset{-}{x_2} \vee x_1)\newline
\mapsto &(x_1 + x_2 + x_3) \cdot (x_4 + (1-x_2) + x_1)
\end{aligned}
$$
A clause is $\text{SAT}$ then the corresponding term $> 0$, a clause is $\overline{\text{SAT}}$ then the corresponding term $=0$.

$$
\begin{aligned}
\forall a_1,\dots,a_n \in \lbrace 0,1\rbrace, \phi(a_1,\dots,a_n) = 1 &\mapsto P(a_1,\dots,a_n) > 0\newline
\forall a_1,\dots,a_n \in \lbrace 0,1\rbrace, \phi(a_1,\dots,a_n) = 0 &\mapsto P(a_1,\dots,a_n) = 0
\end{aligned}
$$

Thus, we consider sum that
$$
\phi \in \text{UN-SAT} \leftrightarrow \sum\limits_{a_1,\dots,a_n} P(a_1,\dots,a_n) = 0
$$
If $\phi \in \text{SAT}$, the sum is at most $2^n 3^m$.

A useful tool here is that $\mathbb{F}$ be a field and $f \in \mathbb{F}\lbrack X \rbrack$ of degree $d$, then $|\text{roots}(f)| \le d$.

$f$ should never be defined over ring since no zero divisor must be satisfied. Check crypto-3-note and here.

We can pick a prime $q > 2^n3^m$ and we will be able to do all the arithmetic over $\mathbb{F}_q$.

Then we want to convince $V$ that $\sum\limits_{a_1,\dots,a_n} P(a_1,\dots,a_n) = 0$ with $P \in \mathbb{F}_q\lbrack X\rbrack$.

Sumcheck Protocol for UNSAT

$\langle P,V \rangle$ has common input $\phi$ and transformed polynomial $P_\phi$. They want to prove $\sum P= 0$.

  • $P$ generates $P_1(x) = \sum\limits_{a_2,\dots,a_n} P_\phi(x, a_2,\dots,a_n)$ to $V$.

  • $V$ checks $P_1(0) + P_1(1) = 0$. $V$ generates $r_1 \overset{R}{\leftarrow}\mathbb{F}_q$ and send to $P$.

    Since $P_1(0) + P_1(1) = \sum\limits_{a_1,\dots,a_n} P_\phi(a_1, a_2,\dots,a_n)$, if $P_\phi$ is unsatisfiable, then $\sum = 0$.

  • $P$ generates $P_2 (x) = \sum\limits_{a_3,\dots,a_n} P_\phi(r_1,x, a_3,\dots,a_n)$ to $V$.

  • $V$ checks $P_2(0) + P_2(1) = P_1(r_1)$. $V$ generates $r_2 \overset{R}{\leftarrow}\mathbb{F}_q$ and send to $P$.

  • $\dots$

  • $P$ generates $P_i(x) = \sum\limits_{a_{i+1}, \dots,a_n} P_\phi(r_1, \dots,r_{i-1},x, a_{i+1},\dots,a_n)$ to $V$.

  • $V$ checks $P_i(0) + P_i(1) = P_{i-1}(r_{i-1})$. ($P_{i-1}(x) = \sum\limits_{a_{i}, \dots,a_n} P_\phi(r_1, \dots,r_{i-2},x, a_{i},\dots,a_n)$)

    $V$ generates $r_{i+1} \overset{R}{\leftarrow} \mathbb{F}_q$ and send to $P$.

  • $\dots$

  • $P$ generates $P_n(x) = P_\phi(r_1,\dots,r_{n-1}, x)$ to $V$.

  • $V$ checks $P_n(0) + P_n(1) = P_{n-1}(r_{n-1})$.

    $V$ samples $r_n \overset{R}{\leftarrow} \mathbb{F}_q$.

    $V$ checks $P_\phi(r_1,\dots,r_n) = P_n(r_n)$.

The efficiency of $V$ is $\text{poly}(n, \text{degree of }P_\phi \le m, |P_\phi|)$.

We need to also prove the completeness and soundness.

Completeness is trivial, $\sum P_\phi = 0,\Pr \lbrack \langle P,V\rangle(\phi, P_\phi) = 1\rbrack = 1$.

Soundness relies on a basis of induction. $\sum P_\phi \neq 0,\Pr \lbrack \langle \overset{\sim}{P},V\rangle(\phi, P_\phi) = 1\rbrack \leq \dfrac{n\cdot m}{q}$.

Claim that $E_i$ be the event that $\overset{\sim}{P_i} = P_i(x) = \sum\limits_{a_{i+1}, \dots,a_n} P_\phi(r_1, \dots,r_{i-1},x, a_{i+1},\dots,a_n)$, $W$ be the event that $\overset{\sim}{P}$ wins.

Claim that $\Pr\lbrack W | E_1 \wedge \dots \wedge E_n\rbrack = 0$. Since $\Pr\lbrack W | E_1 \wedge \dots \wedge E_n\rbrack \le \Pr \lbrack W | E_1 \rbrack$ and $\sum P_\phi > 0$, $\Pr \lbrack W | E_1 \rbrack = 0$.

Claim that $\Pr\lbrack W \rbrack \leq \dfrac{n\cdot m}{q} + \Pr\lbrack W | E_1 \wedge \dots \wedge E_n\rbrack$, which can be proven by induction.

By induction, $\Pr \lbrack W \rbrack \le \dfrac{(n-j+1)\cdot m}{q} + \Pr \lbrack W | E_j \wedge \dots\wedge E_n\rbrack$.

Consider $j = n, \Pr \lbrack W \rbrack = \Pr\lbrack W | E_n \rbrack + \Pr \lbrack W | \overset{-}{E_n}\rbrack$, then consider $\Pr \lbrack W | \overset{-}{E_n}\rbrack$, i.e., $\overset{\sim}{P}$ wins the game and cheated in the last round by $\overset{\sim}{P_n} \neq P_n(x) = P_\phi(r_1, \dots, r_{n-1},x)$.

Then we can notice that two checks must be done in the last round: $\begin{cases}\overset{\sim}{P_n}(0) + \overset{\sim}{P_n}(1) = \overset{\sim}{P_{n-1}}(r_{n-1}) \newline \overset{\sim}{P_n}(r_n) = P_\phi(r_1,\dots,r_n) \end{cases}$ , for $r_n \overset{R}{\leftarrow} \mathbb{F}_q$.

Since we have $\overset{\sim}{P_{n-1}}$ and $r_{n-1}$ clear, we can construct some $\overset{\sim}{P_n}$ to satisfy the first check.

For the second checking, we can see that $(\overset{\sim}{P_n} - P_\phi(r_1,\dots,r_{n-1}))(x)$ has at most $d \le m$ roots. The probability is less then $\dfrac{m}{q}$. Thus $\Pr \lbrack W | \overset{-}{E_n}\rbrack \le \dfrac{m}{q}$.

If $j$ is satisfied that $\Pr \lbrack W \rbrack \le \dfrac{(n-j+1)\cdot m}{q} + \Pr \lbrack W | E_j \wedge \dots\wedge E_n\rbrack$, then we proceed by $\Pr \lbrack W | E_j \wedge \dots\wedge E_n\rbrack = \Pr \lbrack W | E_{j-1} \wedge E_j \wedge \dots\wedge E_n\rbrack + \Pr \lbrack W | \overset{-}{E_{j-1}} \wedge E_j \wedge \dots\wedge E_n\rbrack$.

Since $\Pr \lbrack W | \overset{-}{E_{j-1}} \wedge E_j \wedge \dots\wedge E_n\rbrack \le \dfrac{m}{q}$, $\Pr \lbrack W \rbrack \le \dfrac{(n-(j-1)+1)\cdot m}{q} + \Pr \lbrack W | E_{j-1} \wedge \dots\wedge E_n\rbrack$.

For $\overset{\sim}{P_j}(0) + \overset{\sim}{P_j}(1) = \overset{\sim}{P_{j-1}}(r_{j-1})$, since we are now $\overset{-}{E_{j-1}}$ event, so $\overset{\sim}{P_j} = P_j$ and $\overset{\sim}{P_{j-1}} \neq P_{j-1}$, the probability that $r_{j-1}$ is a root is $\dfrac{m}{q}$.

Thus $\Pr\lbrack W \rbrack \le \dfrac{mn}{q}$.

#SAT Counting Problem

Let’s go beyond $\text{UN-SAT}$ problem for $\sharp\text{SAT}$ counting problem.

Given $\phi$, how many assignments satisfies $\phi$.

The map from $\phi$ to $P$ is given by
$$
x \vee y \vee \neg z \mapsto 1 - (1-x)(1-y)z
$$
Therefore
$$
\sharp \phi = \sum\limits_{a_1,\dots,a_n} P(a_1,\dots,a_n)
$$
The term is $\le 2^n$. We just need to convince the prover that $\sum P = \sharp \phi$. (modify the first round modify $0$ with $\sharp \phi$)

By Toda’s Theorem we notice that $\text{coNP} \subseteq \text{PH}\subseteq \text{P}^{\sharp \text{P}} \subseteq \text{IP}$.

$\text{IP} = \text{PSPACE}$

If we want to prove this, we want to find a problem that is $\text{PSPACE-Complete}$.

TQBF is $\text{PSPACE-Comlete}$.

A qualified boolean formula ($\text{QBF}$) is an expression $\forall x_1 \exists x_2 \forall x_3 \dots \phi(x_1,\dots,x_n)\in\lbrace 0, 1\rbrace$. $\text{TQBF} = \lbrace \phi \text{ be true}\rbrace$.

We first do arithmetization of $\phi$ to some polynomial $p_\phi$. The mapping is similar
$$
\begin{aligned}
x_i &\mapsto x_i\newline
\neg x_i &\mapsto 1 - x_i\newline
x \vee y \vee z &\mapsto 1 - (1-x)(1-y)(1-z)\newline
t_1 \wedge \dots \wedge t_n &\mapsto \prod\limits_{i \in \lbrack n\rbrack} A(t_i)
\end{aligned}
$$
The $P_\phi$ has an individual degree of $3m$.

The arithmetization for $\forall,\exists$ follows
$$
\begin{aligned}
\forall x_n \phi (x_1,\dots,x_n) &\mapsto \prod_{x_n \in \lbrace 0,1\rbrace} P_\phi(x_1,\dots, x_n) \triangleq P_\phi(x_1,\dots,x_n =0) \cdot P_\phi(x_1,\dots, x_n = 1)\newline
\exists x_n \phi (x_1,\dots,x_n) &\mapsto \underset{x_n \in \lbrace 0,1\rbrace}{\huge\amalg} P_\phi(x_1,\dots, x_n) \triangleq 1 - (1 - P_\phi(x_1, \dots, x_n = 0))\cdot(1 - P_\phi(x_1, \dots, x_n = 1))
\end{aligned}
$$
Therefore $\forall x_1\exists x_2 \forall x_3 \dots \phi(x_1,\dots,x_n) \mapsto \prod\limits_{x_1} \underset{x_2}{\large\amalg}\prod\limits_{x_3}\dots P_{\phi}(x_1,\dots,x_n)$. The individual degree is exponential about $n$, which is $2^{n}3m$.

Introduce degree reduction operator $R_x$ to decrease the degree. If $x \in \lbrace 0,1\rbrace$, then $x^p$ for some $p > 0$ is still $x$. Thus we can insert $R_x$ into arithmetization.
$$
\forall x_1\exists x_2 \forall x_3 \dots \phi(x_1,\dots,x_n) \mapsto \prod\limits_{x_1} \underset{x_1}{R} \underset{x_2}{\huge\amalg} \underset{x_1}{R}\underset{x_2}{R} \prod\limits_{x_3}\underset{x_1}{R}\underset{x_2}{R}\underset{x_3}{R}\dots P_{\phi}(x_1,\dots,x_n) \overset{?}{=} 1
$$
This time, the $q$ chosen will be related with just $\text{poly}(m,n)$.

An operator $\mathcal{O} \in \lbrace \Pi_{x_i}, \amalg_{x_i}, R_{x_i} \rbrace^n_{i=1}$, there are $l = \sum\limits^n_{i=1}(i + 1) = \dfrac{n(n+3)}{2}$ operators after the arithmetization for $P_\phi$.

In this way we can write arithmetized $\text{TQPF}$ into $\mathcal{O}_1\dots \mathcal{O}_l P_\phi$.

The protocol largely needs to check whether $v_k = \mathcal{O}_{k+1}\dots O_l P_{\phi, k}$, where $P_{\phi, k}$ is the poly in round $k$. At the end of each round $V$ computes $v_{k+1}$ for next round.

  • Completeness means if $v_k = \mathcal{O}_{k+1}\dots O_l P_{\phi, k}$ is true, then $v_{k+1} = \mathcal{O}_{k+2}\dots O_l P_{\phi, k+1}$ is true up to probability 1.
  • Soundness means if $v_k = \mathcal{O}_{k+1}\dots O_l P_{\phi, k}$ is false, then $v_{k+1} = \mathcal{O}_{k+2}\dots O_l P_{\phi, k+1}$ is false up to probability less then $\dfrac{1}{2}$.

The initialization $v_0 = 1, P_{\phi, 0} = P_\phi$, where the end means $P_{\phi, l} = v_l$. Three situations on $\mathcal{O}$ need to be reconsidered, we can also check this out.

$\mathcal{O}_{k+1} = \prod\limits_{x_i}/\underset{x_i}{\large\amalg}$

In this case, $V$ already stored $v_k$, $V$ need to be convinced this round that $v_k = \mathcal{O}_{k+1}\dots \mathcal{O}_{l}P_{\phi, k}$, where $P_{\phi, k} = P_\phi(r_1,\dots,r_{k-1}, x_k, \dots, x_n)$.

$P$ sends over some polynomial $\overset{\sim}{P}$ to satisfy
$$
\begin{aligned}
\mathcal{O}_{k+1} \overset{\sim}{P} &= \overset{\sim}{P}(0)\cdot\overset{\sim}{P}(1) \overset{?}{=} v_k\newline
&= \prod\limits_{x_k} \underset{x_1}{R}\dots\underset{x_k}{R} \underset{x_{i+1}}{\huge\amalg} \dots P_{\phi}(r_1,\dots,r_{k-1},x_k,\dots ,x_n)
\end{aligned}
$$
$V$ generates $r_k \overset{R}{\leftarrow}\mathbb{F}_q$ and send over to $P$.

$v_{k+1}$ is calculated by following
$$
\begin{aligned}
v_{k+1} &= \underset{x_1}{R}\dots\underset{x_k}{R} \underset{x_{i+1}}{\huge\amalg} \dots P_{\phi}(r_1,\dots,r_{k},x_{k+1},\dots ,x_n)\newline
&= \overset{\sim}{P}(r_{k})
\end{aligned}
$$

Completeness simply follows.

Soundness is similar to sumcheck protocol ($\overset{\sim}{P}$ means a forged polynomial).

If $v_k \neq \prod\limits_{x_k} {\big\lbrace} \underset{x_1}{R}\dots\underset{x_k}{R} \underset{x_{i+1}}{\huge\amalg} \dots P_{\phi}(r_1,\dots,r_{k-1},x_k,\dots ,x_n){\big\rbrace}$, then $P$ must forge $\overset{\sim}{P} \neq \underset{x_1}{R}\dots\underset{x_k}{R} \underset{x_{i+1}}{\huge\amalg} \dots P_{\phi}(r_1,\dots,r_{k-1},x_k,\dots ,x_n)$.

$v_k$ can be used to construct $\overset{\sim}{P}$ but $\overset{\sim}{P}(r_k) = \underset{x_1}{R}\dots\underset{x_k}{R} \underset{x_{i+1}}{\huge\amalg} \dots P_{\phi}(r_1,\dots,r_k, x_{k+1},\dots ,x_n)$ has a probability of $\dfrac{1}{q}$ for degree decreased to 1.

$\mathcal{O}_{k+1} = \underset{x_i}{\large\amalg}$ is similar case.

$\mathcal{O}_{k+1} = \underset{x_i}{R}$

$V$ need to check $v_k = \underset{x_i}{R} \mathcal{O}_{k+2} \dots P_{\phi,k}$, where $P_{\phi, k} = P_\phi(r_1,\dots,r_j, x_{j+1}, \dots, x_n)$ with some $j \ge i$.

$P$ sends over some polynomial $\overset{\sim}{P}(r_i)$ to satisfy
$$
\underset{x_i}{R}\mathcal{O}_{k+2} \dots P_{\phi}(r_1,\dots,r_j, x_{j+1}, \dots,x_n) = v_k \overset{?}{=} \mathcal{O}_{k+1}\overset{\sim}{P} = (\underset{x_i}{R}\overset{\sim}{P})(r_i)
$$
$V$ generates $r_i^{\text{new}} \overset{R}{\leftarrow}\mathbb{F}_q$

  • send $r_i^{\text{new}}$ to $P$
  • $v_{k+1} \triangleq \overset{\sim}{P}(r^{\text{new}}_i)$

$v_{k+1}$ should be equal to $\mathcal{O}_{k+2} \dots P_\phi(r_1,\dots,r_i^{\text{new}},\dots,r_j, x_{j+1}, \dots, x_n)$

Completeness simply follows.

Soundness must holds in
$$
\underset{x_i}{R}\mathcal{O}_{k+2} \dots P_{\phi}(r_1,\dots,r_j, x_{j+1}, \dots,x_n) \neq v_k
$$
If the $\overset{\sim}{P}$ is forged, donate $P_{\text{true}}(r_i) = \mathcal{O}_{k+2} \dots P_\phi(r_1,\dots,r_i,\dots,r_j, x_{j+1}, \dots, x_n)$, we want to see $P_{\text{true}}(r_i) = \overset{\sim}{P}(r_i)$. The probability is $\dfrac{\deg(P_{\text{true}} - \overset{\sim}{P})}{q}$.

For $\deg(P_{\text{true}} - \overset{\sim}{P})$, only the most inner operators would lead to $3m$ degree, the other would just be $2$ degree.

Total Soundness

$\dfrac{1}{q}n$ comes from quantifier arimetization.

$\dfrac{2}{q}\sum\limits^{n-1}_{i=1} i$ comes from degree reduction with polynomial degree 2.

$\dfrac{3m}{q}n$ comes from degree reduction with polynomial degree $3m$.

A total soundness error would be $\dfrac{3mn + n^2}{q}$.

Given the claim that $\text{TQBF}$ is $\text{PSPACE-Complete}$, $\text{PSPACE} \subseteq \text{IP}$.