Impossibility of coin flipping in generalized probabilistic theories via discretizations of semi-infinite programs

Coin flipping is a fundamental cryptographic task where spatially separated Alice and Bob wish to generate a fair coin flip over a communication channel. It is known that ideal coin flipping is impossible in both classical and quantum theory. In this work, we give a short proof that it is also impossible in generalized probabilistic theories under the generalized no-restriction hypothesis. Our proof relies crucially on a formulation of cheating strategies as semi-infinite programs, i.e., cone programs with infinitely many constraints. This introduces a formalism which may be of independent interest to the quantum community.

Figure 1

Alice has two strategy sets $A$ and $A^{\prime }$ corresponding to two different theories. We see that $B$ is equal to both $A^{*}\cap A^o$ and ${\left(A^{\prime }\right)}^{*}\cap {\left(A^{\prime }\right)}^o$ and hence the generalized no-restriction hypothesis for Bob does not imply the same for Alice. We do have that $A=B^{*}\cap B^o$, so sometimes the assumption does hold for both Alice and Bob.