Weak coin flipping with small bias
Iordanis Kerenidis, Ashwin Nayak · 2004
This note presents a quantum protocol that demonstrates that weak coin flipping with bias ≈ 0.239, less than 1/4, is possible. A bias of 1/4 was the smallest known, and followed from the strong coin flipping protocol of Ambainis [2]. Protocols with yet smaller bias ≈ 0.207 have independently been discovered [4, 10]. We also present an alternative strong coin flipping protocol with bias 1/4 with analysis simpler than that of [2]. 1 Quantum weak coin flipping Often in applications based on this primitive, coin-flipping is used to choose one of two competing parties as the “winner”. In the classic example from [5], Alice and Bob are getting a divorce, and would like to decide who gets the car. They decide to toss a coin for that purpose, but don’t trust each other. In such a scenario, they could instead play any fair game to decide the issue. Motivated by this, we consider the following weaker version of coin-flipping. A weak coin flipping protocol with bias ǫ, is a two-party communication game in the style of [11], in which the players start with no inputs, and compute a value cA,cB ∈ {0,1} respectively or declare that the other player is cheating. The protocol is deemed successful if Alice and Bob agree on the outcome, i.e. cA = cB.