Information Trust Institute (ITI) Calendar

Back to Listing

TSS Seminar: Hemanta K. Maji: "On the Computational Complexity of Coin Flipping"

Event Type
Information Trust Institute
3405 Siebel Center
Oct 13, 2010   4:00 pm  
Hemanta K. Maji, University of Illinois
Originating Calendar
Information Trust Institute


Coin flipping is one of the most fundamental tasks in cryptographic protocol design. The problem of (weak) coinflipping was introduced in the seminal work of Blum, who described the task by means of the following scenario: Alice and Bob are divorcing, and have agreed to let the ownership of their favorite car be decided by a coin toss: Heads means that Alice gets the car, and Tails means that Bob gets it. Unfortunately, Alice and Bob are not willing to be in the same room, and need to implement this coin toss over the telephone. As such, Alice and Bob want a protocol such that:

1. The transcript of their conversation uniquely determines who gets the car.
2. If both Alice and Bob behave honestly, then Alice and Bob should both get the car with probability 1/2.
3. If Alice behaves maliciously but Bob behaves honestly, then Alice cannot signicantly increase the probability that she gets the car. Similarly, if Bob behaves maliciously but Alice behaves honestly, then Bob cannot signicantly increase the probability that he gets the car.

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 ipping 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 positive additive constant), the only complexity-theoretic implication that was known was that PSPACE \not\subseteq 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 \not\subseteq 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.


Hemanta K. Maji is a PhD student in the Department of Computer Science at the University of Illinois at Urbana-Champaign. He received his BTech in Computer Science and Engineering from the Indian Institute of Technology, Kanpur. His interests include Cryptography, Coding Theory, and Information Theory. Currently, he is working with Prof. Manoj Prabhakaran on problems in Secure Multi-party Computation and building a framework to study Computational Assumptions.

link for robots only