Amplifying the completeness and soundness of a proof scheme

Question

A (interactive) proof system for a language $\mathcal{L}$ is defined by two algorithms $\mathcal{P}$, a prover, and $\mathcal{V}$, an efficient verifier, with the following requirements:

• Completeness: For $x\in \mathcal{L}$, $\Pr[\mathcal{V}(x, \mathcal{P(x)}) = 1] \geq c$, for some fix constant $c \in (0,1]$.
• Soundness: For $x\notin \mathcal{L}$, $\Pr[\mathcal{V}(x, \mathcal{P(x)}) = 1] \leq s$, for some fix constant $s\in [0,1)$ such that $c-s = \delta>0$.

Note that $\mathcal{V}$ does not necessarily run $\mathcal{P}$ as a subroutine.

It is generally stated that soundness and completeness can be "amplified" by running the proof system on the same instance $x$ multiple times.

Most of the time, the case of soundness is illustrated by saying that the probability that $\mathcal{V}$ outputs $1$ on all $n$ instances will be $s^n$, which to me makes sense in the case we have, for completeness, $x\in \mathcal{L}$, $\Pr[\mathcal{V}(x, \mathcal{P(x)}) = 1] = 1$. Since we know that for $x\in \mathcal{L}$, $\mathcal{V}$ is always going to output $1$ and when $x\notin \mathcal{L}$, with probability $1-s^n$, $\mathcal{V}$ will output $0$.

However, when $0<c<1$, how does repeating the process will help amplify the soundness? and how can it also amplify the completeness given that when $x\in \mathcal{L}$, it is still possible for $\mathcal{V}$ to output $0$.

Answer 1

I will assume that at least $\delta$ is known. $c$ can be estimated by running the proof many times on true statements and $s$ can be set as $c-\delta$. The strategy to make completeness close to $1$ and soundness close to $0$ is as follows:

• Repeat the proof $n$ times. Let $v_1,\dots,v_n$ be the output of $\mathcal{V}$ for each proof. If $\sum_i v_i\geq (c-\frac\delta 2)n$, then output $1$, otherwise output $0$.

We can show that this has the desired completeness and soundness as follows.

Completeness Assume $x\in L$ and let $V_1,\dots,V_n$ be random variables denoting the output of $\mathcal{V}$ for each of the repetition. We have $\mathbb{E}[V_i]\geq c$ for each $i$ by the $c$-completeness of the proof. The probability that we reject is $$ \Pr\left[\sum_i V_i< (c-\frac\delta 2)n\right] =\Pr\left[\sum_i V_i- \mathbb{E}[\sum_i V_i]< -\frac\delta 2 n\right] \leq \exp(-\frac\delta 2 n) $$ The last inequality above is Hoeffding's inequality with $t=\frac \delta 2 n$.

Soundness For $x\notin L$, again let $V_1,\dots,V_n$ be random variables denoting the output of $\mathcal{V}$ for each of the repetition. We have $\mathbb{E}[V_i]\leq s\leq c-\delta$ for each $i$ by the $s$-soundness of the proof. Now, the probability that we accept is (again using Hoeffding) $$ \Pr\left[\sum_i V_i\geq (c-\frac\delta 2)n\right] \leq\Pr\left[\sum_i V_i\geq (s+\frac\delta 2)n\right] =\Pr\left[\sum_i V_i- \mathbb{E}[\sum_i V_i]\geq \frac\delta 2 n\right] $$ which is again upper bounded by $\exp(-\frac\delta 2 n)$.