Paper 2021/1259

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

Thomas Attema, Centrum Wiskunde & Informatica, Netherlands Organisation for Applied Scientific Research
Serge Fehr, Centrum Wiskunde & Informatica, Leiden University
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 2 - February 16, 2022: Corrected a technical oversight by slightly redefining the punctured success probability delta_k and its multi-round variant. In particular, delta_k is now defined as a minimum over all subsets of cardinality exactly k-1, whereas this used to be a minimum over all subsets of cardinality at most k-1. This subtle difference does not affect the analysis of Sigma-protocols (in fact, the actual value of delta_k remains the same), but it turns out to be crucial in the multi-round analysis.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2022
DOI
10.1007/978-3-031-15802-5_15
Keywords
Proofs of KnowledgeKnowledge SoundnessSpecial-SoundnessKnowledge ExtractorParallel RepetitionThreshold Parallel Repetition.
Contact author(s)
thomas attema @ tno nl
serge fehr @ cwi nl
History
2023-09-06: last of 2 revisions
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},
      doi = {10.1007/978-3-031-15802-5_15},
      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.