Security of fixed-weight repetitions of special-sound multi-round interactive proofs

Interactive proofs are a cornerstone of modern cryptography and, as such, used in many areas, from digital signatures to multi-party computation. Often the knowledge error of an interactive proof is not small enough and thus needs to be reduced. This is usually achieved by repeating the interactive proof in parallel t times. Recently, it was shown that the t-fold parallel repetition of any -special-sound multi-round public-coin interactive proof reduces the knowledge error from to , which is optimal. However, parallel repetitions lead to an increase in transcript size. A common technique to mitigate this drawback, which is often employed in digital signatures obtained by using the Fiat–Shamir transform, is to use fixed-weight challenges, i.e. vectors of challenges having a constant number of entries (for which the last component is) equal to a fixed value. While widely used, this method has not been fully assessed from a security standpoint. In particular, the effect of the technique on the knowledge error of repeated interactive proofs has remained unstudied. In this work, we fill the gap and prove that a fixed-weight repetition of a -special-sound multi-round public-coin interactive proof is still knowledge sound. We provide an explicit bound for the knowledge error of the protocol, proving that it matches the maximum cheating probability of a dishonest prover. Our results apply to some recently-proposed digital signatures which are supposed to be quantum resistant, for example the code-based signature CROSS.