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 (k1,…,kμ)-special-sound multi-round public-coin interactive proof reduces the knowledge error from κ to κt, 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 (k1,…,kμ)-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.