TY - GEN
T1 - On the computational complexity of coin flipping
AU - Maji, Hemanta K.
AU - Prabhakaran, Manoj
AU - Sahai, Amit
PY - 2010
Y1 - 2010
N2 - 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 [1], 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 [2], 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 [3]. 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.
AB - 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 [1], 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 [2], 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 [3]. 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.
KW - NP
KW - One-way functions
KW - Weak coin-flipping
UR - http://www.scopus.com/inward/record.url?scp=78751496266&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78751496266&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2010.64
DO - 10.1109/FOCS.2010.64
M3 - Conference contribution
AN - SCOPUS:78751496266
SN - 9780769542447
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 613
EP - 622
BT - Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
PB - IEEE Computer Society
T2 - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Y2 - 23 October 2010 through 26 October 2010
ER -