Welcome to the resource topic for 2024/884
Title:
Security of Fixed-Weight Repetitions of Special-Sound Multi-Round Proofs
Authors: Michele Battagliola, Riccardo Longo, Federico Pintore, Edoardo Signorini, Giovanni Tognolini
Abstract:Interactive proofs are a cornerstone of modern cryptography and as such used in many areas, from digital signatures to multy-party computation. Often the knowledge error \kappa 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 parallel repetition of any (k_1, \ldots , k_\mu)-special-sound multi-round public-coin interactive proof reduces the knowledge error from \kappa to \kappa^t, which is optimal. However, in many cases parallel repetitions lead to a significant increase in transcript size. A common technique to mitigate this drawback, which is often used 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 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 the special-sound repeated interactive proof has remained unstudied. In this work, we fill the gap and prove that a fixed-weight repetition of a (k_1, \ldots, k_\mu)-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 with the cheating probability of a dishonest prover. Our results apply to some recently-proposed digital signatures which are supposed to be quantum resistant, for example CROSS.
ePrint: https://eprint.iacr.org/2024/884
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .