Welcome to the resource topic for 2016/800
Title:
Almost-Optimally Fair Multiparty Coin-Tossing with Nearly Three-Quarters Malicious
Authors: Bar Alon, Eran Omri
Abstract:An \alpha-fair coin-tossing protocol allows a set of mutually distrustful parties to generate a uniform bit, such that no efficient adversary can bias the output bit by more than \alpha. Cleve [STOC 1986] has shown that if half of the parties can be corrupted, then, no r-round coin-tossing protocol is o(1/r)-fair. For over two decades the best known m-party protocols, tolerating up to t\geq m/2 corrupted parties, were only O(t/\sqrt{r})-fair. In a surprising result, Moran, Naor, and Segev [TCC 2009] constructed an r-round two-party O(1/r)-fair coin-tossing protocol, i.e., an optimally fair protocol. Beimel, Omri, and Orlov [Crypto 2010] extended the results of Moran et al.~to the {\em multiparty setting} where strictly fewer than 2/3 of the parties are corrupted. They constructed a 2^{2^k}/r-fair r-round m-party protocol, tolerating up to t=\frac{m+k}{2} corrupted parties. Recently, in a breakthrough result, Haitner and Tsfadia [STOC 2014] constructed an O(\log^3(r)/r)-fair (almost optimal) three-party coin-tossing protocol. Their work brings forth a combination of novel techniques for coping with the difficulties of constructing fair coin-tossing protocols. Still, the best coin-tossing protocols for the case where more than 2/3 of the parties may be corrupted (and even when t=2m/3, where m>3) were \theta(1/\sqrt{r})-fair. We construct an O(\log^3(r)/r)-fair m-party coin-tossing protocol, tolerating up to t corrupted parties, whenever m is constant and t<3m/4.
ePrint: https://eprint.iacr.org/2016/800
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .