International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 12 October 2021

Thomas Attema, Serge Fehr, Michael Klooß
ePrint Report ePrint Report
The celebrated Fiat-Shamir transformation turns any public-coin interactive proof into an 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 parallel repetitions of typical $(k_1, \ldots, k_\mu)$-special-sound protocols, there is an attack which results in a security loss of about $(Q/\mu)^\mu \mu^{-t}$, assuming for simplicity that $t$ is an integer multiple of $\mu$.

Additional news items may be found on the IACR news page.