Parallel repetition of (k_1, ...,k_\mu)-special-sound multi-round interactive proofs

In many occasions, the knowledge error κ of an interactive proof is not small enough, and thus needs to be reduced. This can be done generically by repeating the interactive proof in parallel. While there have been many works studying the effect of parallel repetition on the soundness error of interactive proofs and arguments, the effect of parallel repetition on the knowledge error has largely remained unstudied. Only recently it was shown that the t-fold parallel repetition of any interactive protocol reduces the knowledge error from κ down to κ^t+ν for any non-negligible term ν. This generic result is suboptimal in that it does not give the knowledge error κ^t that one would expect for typical protocols, and, worse, the knowledge error remains non-negligible. In this work we show that indeed the t-fold parallel repetition of any (k_1,…,k_μ)-special-sound multi-round public-coin interactive proof optimally reduces the knowledge error from κ down to κ^t. At the core of our results is an alternative, in some sense more fine-grained, measure of quality of a dishonest prover than its success probability, for which we show that it characterizes when knowledge extraction is possible. This new measure then turns out to be very convenient when it comes to analyzing the parallel repetition of such interactive proofs. While parallel repetition reduces the knowledge error, it is easily seen to increase the completeness error. For this reason, we generalize our result to the case of s-out-of-t threshold parallel repetition, where the verifier accepts if s out of t of the parallel instances are accepting. An appropriately chosen threshold s allows both the knowledge error and completeness error to be reduced simultaneously.

• View at Publisher

Full Text ( Final Version , 209kb )