Coin Flipping of \emph{Any} Constant Bias Implies One-Way Functions
This addresses a foundational problem in cryptography by linking coin-flipping to one-way functions, which is crucial for secure communication and protocols, representing a significant theoretical advance rather than an incremental improvement.
The paper tackles the problem of establishing a connection between coin-flipping protocols with any constant bias and one-way functions, showing that such protocols imply the existence of one-way functions, improving upon a previous result that required bias below approximately 0.207.
We show that the existence of a coin-flipping protocol safe against \emph{any} non-trivial constant bias (\eg $.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 \emph{weak} coin-flipping protocols.