TY - GEN

T1 - On the computational complexity of coin flipping

AU - Maji, Hemanta K.

AU - Prabhakaran, Manoj

AU - Sahai, Amit

PY - 2010/12/1

Y1 - 2010/12/1

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

T2 - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

Y2 - 23 October 2010 through 26 October 2010

ER -