Welcome to the resource topic for 2023/818
Title:
A Generalized Special-Soundness Notion and its Knowledge Extractors
Authors: Thomas Attema, Serge Fehr, Nicolas Resch
Abstract:A classic result in the theory of interactive proofs shows that a special-sound \Sigma-protocol is automatically a proof of knowledge. This result is very useful to have, since the latter property is typically tricky to prove from scratch, while the former is often easy to argue—if it is satisfied. While classic \Sigma-protocols often are special-sound, this is unfortunately not the case for many recently proposed, highly efficient interactive proofs, at least not in this strict sense. Motivated by this, the original result was recently generalized to k-special sound \Sigma-protocols (for arbitrary, polynomially bounded k), and to multi-round versions thereof. This generalization is sufficient to analyze (e.g.) Bulletproofs-like protocols, but is still insufficient for many other examples.
In this work, we push the relaxation of the special soundness property to the extreme, by allowing an arbitrary access structure \Gamma to specify for which subsets of challenges it is possible to compute a witness, when given correct answers to these challenges (for a fixed first message). Concretely, for any access structure \Gamma, we identify parameters t_\Gamma and \kappa_\Gamma, and we show that any \Gamma-special sound \Sigma-protocol is a proof of knowledge with knowledge error \kappa_\Gamma if t_\Gamma is polynomially bounded. Similarly for multi-round protocols.
We apply our general result to a couple of simple but important example protocols, where we obtain a tight knowledge error as an immediate corollary. Beyond these simple examples, we analyze the FRI protocol. Here, showing the general special soundness notion is non-trivial, but can be done (for a certain range of parameters) by recycling some of the techniques used to argue ordinary soundness of the protocol (as an IOP). Again as a corollary, we then derive that the FRI protocol, as an interactive proof by using a Merkle-tree commitment, is a proof of knowledge with almost optimal knowledge error.
Finally, building up on the technique for the parallel repetition of k-special sound \Sigma-protocols, we show the same strong parallel repetition result for \Gamma-special sound \Sigma-protocol and its multi-round variant.
ePrint: https://eprint.iacr.org/2023/818
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 .