Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Annual Symposium on Foundations of Computer Science

Coin Flipping with Constant Bias Implies One-Way Functions

Iftach Haitner, Eran Omri

Published Oct 1, 2011• 18 citations
Publisher

Abstract

It is well known (cf., Impagliazzo and Luby [FOCS '89]) that the existence of almost all "interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [FOCS '10] proved the same for constant-round protocols (with any non-trivial bias). For the general case, however, no such implication was known. We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, (√2 -1)/2 - o(1)) imply one-way functions.

DOI
10.1109/focs.2011.29

Related papers

Coin Flipping with Constant Bias Implies One-Way Functions

Iftach Haitner, Eran Omri

It is well known (cf. Impagliazzo and Luby [in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 230--235]) that the existence of almost all “interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [in Proceedings of the 2001 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 613--622] proved the same for constant-round protocols (with any nontrivial bias). For the general case, however, no such implication was known. We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, $\frac{\sqrt2 -1}2 - o(1)$) imply one-way functions.

SIAM Journal on Computing•Jan 1, 2014•17 citations

Coin flipping of any constant bias implies one-way functions

Itay Berman, Iftach Haitner, Aris Tentes

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 [EQUATION] -- o(1) ≈ .207. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.

ACM Symposium on Theory of Computing (STOC)•May 31, 2014•10 citations

Coin Flipping of \emph{Any} Constant Bias Implies One-Way Functions

Itay Berman, Iftach Haitner, Aris Tentes

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.

arXiv:2105.01400•May 4, 2021•0 citations

On the Computational Complexity of Coin Flipping

Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai

Coin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo, surprisingly little is known about this question. Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then one-way functions must exist. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant ε > 0), the only complexity-theoretic implication that was known was that PSPACE ⊈ BPP. We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than 1/4 - ε implies that NP ⊈ BPP. Furthermore, for constant-round protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) one-way functions.

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•29 citations

Coin Flipping of Any Constant Bias Implies One-Way Functions

Itay Berman, Iftach Haitner, Aris Tentes

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.

Journal of the ACM•Mar 13, 2018•12 citations

Coin Flipping of Any Constant Bias Implies One-Way Functions.

Itay Berman, Iftach Haitner, Aris Tentes

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) t .207. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.

Electronic colloquium on computational complexity•Jan 1, 2015•1 citation
It is well known (cf., Impagliazzo and Luby [FOCS '89]) that the existence of almost all "interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [FOCS '10] proved the same for constant-round protocols (with any non-trivial bias). For the general case, however, no such implication was known. We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, (√2 -1)/2 - o(1)) imply one-way functions.
It is well known (cf. Impagliazzo and Luby [in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 230--235]) that the existence of almost all “interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [in Proceedings of the 2001 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 613--622] proved the same for constant-round protocols (with any nontrivial bias). For the general case, however, no such implication was known. We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, 2−12−o(1)\frac{\sqrt2 -1}2 - o(1)22​−1​−o(1)) imply one-way functions.
We show that the existence of a coin-flipping protocol safe against \emph{any} non-trivial constant bias (\eg .499.499.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 2−12−o(1)≈.207\frac{\sqrt2 -1}2 - o(1) \approx .20722​−1​−o(1)≈.207. Unlike the result of Haitner and Omri, our result also holds for \emph{weak} coin-flipping protocols.
Coin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo, surprisingly little is known about this question. Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then one-way functions must exist. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant ε > 0), the only complexity-theoretic implication that was known was that PSPACE ⊈ BPP. We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than 1/4 - ε implies that NP ⊈ BPP. Furthermore, for constant-round protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) one-way functions.