Welcome to the resource topic for 2021/1259
Title:
Parallel Repetition of (k_1,\dots,k_{\mu})-Special-Sound Multi-Round Interactive Proofs
Authors: Thomas Attema, Serge Fehr
Abstract:In many occasions, the knowledge error \kappa 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 {\em soundness error} of interactive proofs and arguments, the effect of parallel repetition on the {\em knowledge error} has largely remained unstudied. Only recently it was shown that the t-fold parallel repetition of {\em any} interactive protocol reduces the knowledge error from \kappa down to \kappa^t +\nu for any non-negligible term \nu. This generic result is suboptimal in that it does not give the knowledge error \kappa^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,\dots,k_{\mu})-special-sound multi-round public-coin interactive proof optimally reduces the knowledge error from \kappa down to \kappa^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 {\em increase} the {\em 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.
ePrint: https://eprint.iacr.org/2021/1259
Talk: https://www.youtube.com/watch?v=hh9GxJcks_Y
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/29/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .