1
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ What "flavor" of parallel repetition is this? Is the prover required to succeed in all instances? (Which seems to be the case). $\endgroup$ Commented Dec 22, 2022 at 0:18
  • $\begingroup$ @MarcIlunga Yeah, I forgot to mention that. I edited the text, so you are right. $\endgroup$
    – Bean Guy
    Commented Dec 22, 2022 at 6:54

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.