Coin Flipping of Any Constant Bias Implies One-Way Functions
Itay Berman, Iftach Haitner, Aris Tentes · Journal of the ACM · 2018
We show that the existence of a coin-flipping protocol safe against any nontrivial constant bias (e.g., .499) implies the existence of one-way functions. This improves upon a result of Haitner and Omri (FOCS’11), who proved this implication for protocols with bias √ 2−1/2 − o (1) ≈ .207. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.