Coin Flipping of Any Constant Bias Implies One-Way Functions

2021/05/04 by Itay Berman, Berman, Itay, Iftach Haitner +3
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2105.01400

openalex publication_date 2021/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the existence of a coin-flipping protocol safe against 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√2 -12 - o(1) ≈ .207. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.

Related

• On the Complexity of Fair Coin Flipping
• Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling
• Weak coin flipping with small bias
• Quantum coin flipping with arbitrary small bias is impossible
• Quantum weak coin-flipping with bias of 0.192