Fair Coin Flipping: Tighter Analysis and the Many-Party Case

Abstract In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some adversarial parties try to bias the output. In this work, we focus on the case of an arbitrary number of corrupted parties. Cleve [20] [STOC 1986] has shown that in any such m -round coin-flipping protocol, the corrupted parties can bias the honest parties’ common output bit by $$\Theta (1/m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . For more than two decades, however, the best-known coin-flipping protocol was the one of Awerbuch, Blum, Chor, Goldwasser, and Micali [10] [Manuscript 1985], who presented a t -party, m -round protocol with bias $$\Theta (t/\sqrt{m})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>/</mml:mo> <mml:msqrt> <mml:mi>m</mml:mi> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . This was changed by the breakthrough result of Moran, Naor, and Segev [51] [Journal of Cryptology 2016], who constructed an m -round, two -party coin-flipping protocol with optimal bias $$\Theta (1/m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . More recently, Haitner and Tsfadia [37] [SIAM Journal on Computing 2017] constructed an m -round, three -party coin-flipping protocol with bias $$O(\log ^3m / m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>3</mml:mn> </mml:msup> <mml:mi>m</mml:mi> <mml:mo>/</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Still for the case of more than three parties, the best-known protocol remained the $$\Theta (t/\sqrt{m})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>/</mml:mo> <mml:msqrt> <mml:mi>m</mml:mi> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -bias protocol of [10]. We make a step toward eliminating the above gap, presenting a t -party, m -round coin-flipping protocol, with bias $$O\left( \frac{t^4 \cdot 2^t \cdot \sqrt{\log m}}{m^{1/2+1/(2^{t-1}-2)}}\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:mfrac> <mml:mrow> <mml:msup> <mml:mi>t</mml:mi> <mml:mn>4</mml:mn> </mml:msup> <mml:mo>·</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>t</mml:mi> </mml:msup> <mml:mo>·</mml:mo> <mml:msqrt> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> </mml:msqrt> </mml:mrow> <mml:msup> <mml:mi>m</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mo>(</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:mfrac> </mml:mfenced> </mml:mrow> </mml:math> for any $$t\le \tfrac{1}{2} \cdot \operatorname {loglog}m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>≤</mml:mo> <mml:mstyle> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:mfrac> </mml:mstyle> <mml:mo>·</mml:mo> <mml:mo>loglog</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> </mml:math> . This improves upon the