Alice and Bob want to flip a coin but they do not trust one another. They want to have a protocol that would produce each of two results (0 and 1) with probability 1/2 each if both Alice and Bob follow the protocol. If one of them follows the protocol but the other does not, the person who follows the protocol is guaranteed that each outcome has probability at most 1/2 + epsilon. In classical (non-quantum) cryptography, this can be done but requires complexity assumptions (such as existence of one-way permutations). We study the question whether quantum mechanics makes it possible to perform coin flipping with an information theoretic security instead of computational.

Mayers, Salvail and Chiba-Kohno showed that there is no quantum protocol that achieves epsilon = 0. However, arbitrarily small epsilon > 0 might be achievable. In this talk, I will present two new results about quantum coin flipping. First, I will show a simple quantum protocol for coin flipping in which no cheating party can achieve one outcome (0 or 1) with probability more than 0.75. This is the best provable result known and it improves the previous 0.91...of Aharonov, Ta-Shma, Vazirani and Yao (STOC'00.) I will also show that the new protocol is optimal for a restricted class of protocols.

Second, I will show a general lower bound on how good can be protocols that are restricted to k messages between Alice and Bob. This bound implies that, to decrease the bias epsilon, one needs to increase the number of messages (rounds), not just exchange a lot of qubits in few rounds.