Paper 2024/884

Security of Fixed-Weight Repetitions of Special-Sound Multi-Round Proofs

Michele Battagliola, Università Politecnica delle Marche
Riccardo Longo, Fondazione Bruno Kessler, Center for Cybersecurity
Federico Pintore, Università di Trento
Edoardo Signorini, Telsy, Politecnico di Torino
Giovanni Tognolini, Università di Trento
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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
knowledge soundnessfixed-weight repetitionspecial-soundnessproof of knowledgepost-quantumdigital signatures
Contact author(s)
battagliola michele @ proton me
rlongo @ fbk eu
federico pintore @ unitn it
edoardo signorini @ telsy it
giovanni tognolini @ unitn it
History
2024-06-05: approved
2024-06-03: received
See all versions
Short URL
https://ia.cr/2024/884
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/884,
      author = {Michele Battagliola and Riccardo Longo and Federico Pintore and Edoardo Signorini and Giovanni Tognolini},
      title = {Security of Fixed-Weight Repetitions of Special-Sound Multi-Round Proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/884},
      year = {2024},
      url = {https://eprint.iacr.org/2024/884}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.