Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
On the Complexity of Fair Coin Flipping
verfasst von : Iftach Haitner, Nikolaos Makriyannis, Eran Omri
Erschienen in: Theory of Cryptography
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A two-party coin-flipping protocol is \(\varepsilon \)-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than \(\varepsilon \). Cleve [STOC ’86] showed that r-round o(1 / r)-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript ’85] constructed a \(\varTheta (1/\sqrt{r})\)-fair coin-flipping protocol, assuming the existence of one-way functions. Moran et al. [Journal of Cryptology ’16] constructed an r-round coin-flipping protocol that is \(\varTheta (1/r)\)-fair (thus matching the aforementioned lower bound of Cleve [STOC ’86]), assuming the existence of oblivious transfer.
The above gives rise to the intriguing question of whether oblivious transfer, or more generally “public-key primitives”, is required for an \(o(1/\sqrt{r})\)-fair coin flipping. This question was partially answered by Dachman-Soled et al. [TCC ’11] and Dachman-Soled et al. [TCC ’14], who showed that restricted types of fully black-box reductions cannot establish \(o(1/\sqrt{r})\)-fair coin-flipping protocols from one-way functions. In particular, for constant-round coin-flipping protocols, [10] yields that black-box techniques from one-way functions can only guarantee fairness of order \(1/\sqrt{r}\).
We make progress towards answering the above question by showing that, for any constant
, the existence of an \(1/(c\cdot \sqrt{r})\)-fair, r-round coin-flipping protocol implies the existence of an infinitely-often key-agreement protocol, where c denotes some universal constant (independent of r). Our reduction is non black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner et al. [FOCS ’18] to facilitate a two-party variant of the attack of Beimel et al. [FOCS ’18] on multi-party coin-flipping protocols.
, the existence of an \(1/(c\cdot \sqrt{r})\)-fair, r-round coin-flipping protocol implies the existence of an infinitely-often key-agreement protocol, where c denotes some universal constant (independent of r). Our reduction is non black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner et al. [FOCS ’18] to facilitate a two-party variant of the attack of Beimel et al. [FOCS ’18] on multi-party coin-flipping protocols.