Paper 2021/1259

Parallel Repetition of $(k_1,\dots,k_{\mu})$-Special-Sound Multi-Round Interactive Proofs

Thomas Attema and 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.

Note: Change log w.r.t. Version 1 - September 20, 2021: More elaborate comparison with prior works and editorial changes throughout.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
Proofs of KnowledgeKnowledge SoundnessSpecial-SoundnessKnowledge ExtractorParallel RepetitionThreshold Parallel Repetition.
Contact author(s)
thomas attema @ tno nl
serge fehr @ cwi nl
History
2022-02-16: revised
2021-09-21: received
See all versions
Short URL
https://ia.cr/2021/1259
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1259,
      author = {Thomas Attema and Serge Fehr},
      title = {Parallel Repetition of $(k_1,\dots,k_{\mu})$-Special-Sound Multi-Round Interactive Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1259},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1259}},
      url = {https://eprint.iacr.org/2021/1259}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.