English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 theoutput. In this work we focus on the case of an arbitrary number of corruptedparties. Cleve [STOC 1986] has shown that in any such $m$-round coin-flippingprotocol, the corrupted parties can bias the honest parties' common output bitby $\Theta(1/m)$. For more than two decades, the best known coin-flippingprotocol was the one of Awerbuch et al. [Manuscript 1985], who presented a$t$-party, $m$-round protocol with bias $\Theta(t/\sqrt{m})$. This was changedby the breakthrough result of Moran et al. [TCC 2009], who constructed an$m$-round, two-party coin-flipping protocol with optimal bias $\Theta(1/m)$.Haitner and Tsfadia [STOC 2014] constructed an $m$-round, three-partycoin-flipping protocol with bias $O(\log^3m / m)$. Still for the case of morethan three parties, the best known protocol remained the$\Theta(t/\sqrt{m})$-bias protocol of Awerbuch et al.  We make a step towards eliminating the above gap, presenting a $t$-party,$m$-round coin-flipping protocol, with bias $O(\frac{t^4 \cdot 2^t \cdot\sqrt{\log m}}{m^{1/2+1/\left(2^{t-1}-2\right)}})$ for any $t\le \tfrac12\log\log m$. This improves upon the $\Theta(t/\sqrt{m})$-bias protocol ofAwerbuch et al., and in particular, for $t\in O(1)$ it is an $1/m^{\frac12 +\Theta(1)}$-bias protocol. For the three-party case, it is an $O(\sqrt{\logm}/m)$-bias protocol, improving over the $O(\log^3m / m)$-bias protocol ofHaitner and Tsfadia.  Our protocol generalizes that of Haitner and Tsfadia, by presenting anappropriate recovery protocol for the remaining parties to interact in, in thecase that some parties abort or are caught cheating. We prove the fairness ofthe new protocol by presenting a new paradigm for analyzing fairness ofcoin-flipping protocols.

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