Paper 2021/1377

Fiat-Shamir Transformation of Multi-Round Interactive Proofs

Thomas Attema, Serge Fehr, and Michael Klooß


The celebrated Fiat-Shamir transformation turns any public-coin interactive proof into a non-interactive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3-move public-coin interactive proofs, i.e., so-called $\Sigma$-protocols, it is now applied to multi-round 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)$-special-sound 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)$-special-sound 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.

Available format(s)
Cryptographic protocols
Publication info
(Non) Interactive ProofsSpecial-SoundnessFiat-Shamir Transformation
Contact author(s)
thomas attema @ tno nl
serge fehr @ cwi nl
michael klooss @ kit edu
2022-02-16: last of 2 revisions
2021-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomas Attema and Serge Fehr and Michael Klooß},
      title = {Fiat-Shamir Transformation of Multi-Round Interactive Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1377},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.