Generalized Special-Sound Interactive Proofs and Their Knowledge Soundness

A classic result in the theory of interactive proofs shows that a special-sound Σ -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 Σ -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 Σ -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 Γ 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 Γ, we identify parameters t_Γ and κ_Γ, and we show that any Γ -special-sound Σ -protocol is a proof of knowledge with knowledge error κ_Γ if t_Γ 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 Σ -protocols, we show the same strong parallel repetition result for Γ -special-sound Σ -protocol and its multi-round variant.