On the computational complexity of coin flipping

Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Pages613-622
Number of pages10
DOIs
StatePublished - Dec 1 2010
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, NV, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
CountryUnited States
CityLas Vegas, NV
Period10/23/1010/26/10

Keywords

  • NP
  • One-way functions
  • Weak coin-flipping

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the computational complexity of coin flipping'. Together they form a unique fingerprint.

Cite this