Fix an interactive proof system $(P,V)$ and denote by $(P_k,V_k)$ an interactive proof system in which the parties play in parallel $k$ copies of $(P,V)$ and for which $V_k$ accepts if and only if $V$ would have accepted in all $k$ copies. The Parallel Repetition Theorem says that given a prover $P$ and input $x$ to the proof system: $$\text{If } \Pr[(P^*,V)(x)=1] \leq \epsilon, \text{ then } \Pr[(P^*,V_k)(x)=1] \leq \epsilon^k.$$ However, I do not understand why this should hold true in the (worst) case that $P^*$ plays with $V_k$ $k-1$ "good" copies of $(P,V)$ and $1$ "bad" copy. Shouldn't the soundness bound in that case be $\epsilon^2 < \Pr[(P^*,V_k)(x)=1] \leq \epsilon$?
-
$\begingroup$ What "flavor" of parallel repetition is this? Is the prover required to succeed in all instances? (Which seems to be the case). $\endgroup$– Marc IlungaCommented Dec 22, 2022 at 0:18
-
$\begingroup$ @MarcIlunga Yeah, I forgot to mention that. I edited the text, so you are right. $\endgroup$– Bean GuyCommented Dec 22, 2022 at 6:54
1 Answer
Assuming we are not too concerned by the constraints of computational proof systems, parallel repetition emulates $k$ independent interactions, and the parallel verifier accepts only if all interactions are accepting.
For this validation strategy (contrasting with the worst-case scenario of the question) and assuming the independence condition, the soundness error is similar to the probability of $k$ successes in $k$ repeated Bernoulli trials, which gives the desired soundness error of $\epsilon^k$.
For considerations on other types of interactive proofs: see here.