The Fiat—Shamir Transformation of (₁, , _) -Special-Sound Interactive Proofs

Abstract The Fiat–Shamir transformation is a general principle to turn any public-coin interactive proof into non-interactive one (with security then typically analyzed in the random oracle model). While initially used for 3-round protocols, many recent constructions use it for multi-round protocols. However, in general the soundness error of the Fiat–Shamir transformed protocol degrades exponentially in the number of rounds. On the positive side, it was shown that for the special class of (k₁, , k_) (k 1, ⋯, k μ) -special-sound Σ -protocols, which is a natural multi-round generalization of the well-known class of special-sound protocols, the loss is actually only linear in the number of random oracle queries, and independent of the number of rounds, which is optimal. A natural next question is whether this positive result extends to the Fiat–Shamir transformation of so-called (₁, , _) (Γ 1, ⋯, Γ μ) -special-sound protocols. This notion was recently defined and analyzed in the interactive case; it captures a larger class of protocols, namely where the special-soundness property is characterized by a general access structure, rather than a threshold. We show in this work that this is indeed the case. Concretely, we show that the Fiat–Shamir transformation of any (₁, , _) (Γ 1, …, Γ μ) -special-sound interactive proof is knowledge sound under the same condition on ₁, , _ Γ 1, ⋯, Γ μ for which the original interactive proof is knowledge sound. Furthermore, also here the loss is linear in the number of random oracle queries and independent of the number of rounds. In light of the above, one might suspect that our argument follows as a straightforward combination of the above mentioned prior works. However, this is not the case. The approach used for (k₁, , k_) (k 1, ⋯, k μ) -special-sound protocols, which is based on an extractor that samples without replacement, does not (seem to) generalize; on the other hand, the other approach, which uses an extractor based on sampling with replacement, comes with an additional loss that would blow up in the recursive multi-round analysis. Thus, new techniques are necessary to handle the above complications.