Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-106 | 21st March 2018 17:08

Coin Flipping of Any Constant Bias Implies One-Way Functions

RSS-Feed




Revision #1
Authors: Itay Berman, Iftach Haitner, Aris Tentes
Accepted on: 21st March 2018 17:08
Downloads: 80
Keywords: 


Abstract:

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.



Changes to previous version:

Simplifications and structure changes in section 4.


Paper:

TR15-106 | 22nd June 2015 11:02

Coin Flipping of Any Constant Bias Implies One-Way Functions





TR15-106
Authors: Itay Berman, Iftach Haitner, Aris Tentes
Publication: 23rd June 2015 21:57
Downloads: 633
Keywords: 


Abstract:

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.



ISSN 1433-8092 | Imprint