Generalized Special-Sound Interactive Proofs and Their Knowledge Soundness

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.) Bulletproofslike 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, has a knowledge extractor with almost optimal knowledge error, with the caveat that the extractor requires (expected) quasi-polynomial time. 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.