Paper 2021/1377
FiatShamir Transformation of MultiRound Interactive Proofs
Thomas Attema, Serge Fehr, and Michael Klooß
Abstract
The celebrated FiatShamir transformation turns any publiccoin interactive proof into a noninteractive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3move publiccoin interactive proofs, i.e., socalled $\Sigma$protocols, it is now applied to multiround protocols as well. Unfortunately, the security loss for a $(2\mu + 1)$move protocol is, in general, $Q^\mu$, where $Q$ is the number of oracle queries performed by the attacker. In general, this is the best one can hope for, as it is easy to see that this loss applies to the $\mu$fold sequential repetition of $\Sigma$protocols, but it raises the question whether certain (natural) classes of interactive proofs feature a milder security loss. In this work, we give positive and negative results on this question. On the positive side, we show that for $(k_1, \ldots, k_\mu)$specialsound protocols (which cover a broad class of use cases), the knowledge error degrades linearly in $Q$, instead of $Q^\mu$. On the negative side, we show that for $t$fold \emph{parallel repetitions} of typical $(k_1, \ldots, k_\mu)$specialsound protocols with $t \geq \mu$ (and assuming for simplicity that $t$ and $Q$ are integer multiples of $\mu$), there is an attack that results in a security loss of approximately~$\frac12 Q^\mu /\mu^{\mu+t}$.
Note: Change log w.r.t. Version 1  October 11, 2021: Simpler proof of Lemma 2, more precise treatment of the attack in Section 7 (some details have been moved to appendix), considering adaptive security as well, and editorial changes throughout.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 (Non) Interactive ProofsSpecialSoundnessFiatShamir Transformation
 Contact author(s)

thomas attema @ tno nl
serge fehr @ cwi nl
michael klooss @ kit edu  History
 20220216: last of 2 revisions
 20211012: received
 See all versions
 Short URL
 https://ia.cr/2021/1377
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1377, author = {Thomas Attema and Serge Fehr and Michael Klooß}, title = {FiatShamir Transformation of MultiRound Interactive Proofs}, howpublished = {Cryptology ePrint Archive, Paper 2021/1377}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1377}}, url = {https://eprint.iacr.org/2021/1377} }