We consider information-theoretically secure quantum protocols for coin flipping. In the two-party case, there is a protocol in which no cheating party can fix the result to one value with probability more than 3/4. In contrast, in any classical protocol, one party can successfully cheat with probability 1. We study the multiparty case when there are k parties and up to k-1 of them may be dishonest. We show that, even in this case, dishonest parties do not have a complete control over the outcome of the protocol. That is, we construct a protocol in which k-1 cheating parties can succesfully fix the outcome of the protocol with probability at most 1 − Ω(1/k). We also show that this is optimal. In our analysis, we introduce a new problem: two party coin flipping with a penalty for cheating. We design a protocol for this problem which we then use to design the multiparty protocol. We expect that this approach may be useful elsewhere. We also discuss the possibility of quantum protocols for oblivious transfer in which no party can successfully cheat with probability 1.

Parts of this talk are joint work with Harry Buhrman, Yevgeniy Dodis, Hein Rohrig and Ran Canetti.