Coin Flipping of Any Constant Bias Implies One-Way Functions
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 13, 2018
- Source ID
- 10.1145/2979676
Entities
People
- Aris Tentes
- Iftach Haitner
- Itay Berman
Organizations
- Army Research Office
- Defense Advanced Research Projects Agency
- Israel Science Foundation
- Israeli Centers for Research Excellence
- Massachusetts Institute of Technology
- National Science Foundation
- Tel Aviv University