International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Eran Omri

Affiliation: Ariel University

Publications

Year
Venue
Title
2018
JOFC
2018
JOFC
2018
TCC
On the Complexity of Fair Coin Flipping
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})$$Θ(1/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)$$Θ(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})$$o(1/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})$$o(1/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}$$1/r.We make progress towards answering the above question by showing that, for any constant , the existence of an $$1/(c\cdot \sqrt{r})$$1/(c·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.
2017
ASIACRYPT
2016
TCC
2016
TCC
2016
JOFC
2015
JOFC
2015
EPRINT
2015
TCC
2015
CRYPTO
2014
EPRINT
2013
TCC
2012
ASIACRYPT
2011
CRYPTO
2010
CRYPTO
2008
CRYPTO

Program Committees

TCC 2018