Paper 2023/818

Generalized Special-Sound Interactive Proofs and their Knowledge Soundness

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. We show a similar result for multi-round $(\Gamma_1,\dots,\Gamma_\mu)$-special-sound interactive proofs. 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_1,\dots,k_\mu)$-special-sound interactive proofs, we show the same strong parallel repetition result for $(\Gamma_1,\dots,\Gamma_\mu)$-special-sound interactive proofs.

Note: Change log w.r.t. Version 2 - September 20, 2023: Revised the incorrect claim that our generalization does not capture parallel repetition of $\Sigma$-protocols; it turns out that our techniques also provide efficient knowledge extraction for the the parallel repetition of $k$-special-sound $\Sigma$-protocols. Further, we made editorial changes throughout the manuscript. Change log w.r.t. Version 1 - June 2, 2023: Corrected a technical oversight by redefining the punctured success probability $\delta_\Gamma$ for multi-round interactive proofs (Equation 5), remarked that the extractor of the FRI-protocol runs in expected quasi-polynomial instead of polynomial time, and editorial changes throughout.