Fiat–Shamir Transformation of Multi-Round Interactive Proofs (Extended Version)

Abstract

Abstract 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 $$\varSigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Σ</mml:mi></mml:math> -protocols, it is now applied to multi-round protocols as well. Unfortunately, the security loss for a $$(2\mu + 1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mn>2</mml:mn><mml:mi>μ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math> -move protocol is, in general, approximately $$Q^\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>Q</mml:mi><mml:mi>μ</mml:mi></mml:msup></mml:math> , 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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>μ</mml:mi></mml:math> -fold sequential repetition of $$\varSigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Σ</mml:mi></mml:math> -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 )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>k</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>k</mml:mi><mml:mi>μ</mml:mi></mml:msub><mml:mo>)</mml:mo></mml:mrow></mml:math> -special-sound protocols (which cover a broad class of use cases), the knowledge error degrades linearly in Q , instead of $$Q^\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>Q</mml:mi><mml:mi>μ</mml:mi></mml:msup></mml:math> . On the negative side, we show that for t -fold parallel repetitions of typical $$(k_1, \ldots , k_\mu )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>k</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>k</mml:mi><mml:mi>μ</mml:mi></mml:msub><mml:mo>)</mml:mo></mml:mrow></mml:math> -special-sound protocols with $$t \ge \mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>t</mml:mi><mml:mo>≥</mml:mo><mml:mi>μ</mml:mi></mml:mrow></mml:math> (and assuming for simplicity that t and Q are integer multiples of $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>μ</mml:mi></mml:math> ), there is an attack that results in a security loss of approximately $$\frac{1}{2} Q^\mu /\mu ^{\mu +t}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mfrac><mml:mn>1</mml:mn><mml:mn>2</mml:mn></mml:mfrac><mml:msup><mml:mi>Q</mml:mi><mml:mi>μ</mml:mi></mml:msup><mml:mo>/</mml:mo><mml:msup><mml:mi>μ</mml:mi><mml:mrow><mml:mi>μ</mml:mi><mml:mo>+</mml:mo><mml:mi>t</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math> .

Topics & Concepts