We focus on a family of quantum coin-flipping protocols based on quantum bit-commitment. We discuss how the semidefinite programming formulations of cheating strategies can be reduced to optimizing a linear combination of fidelity functions over a polytope. These turn out to be much simpler semidefinite programs which can be modelled using second-order cone programming problems. We then use these simplifications to construct their point games as developed by Kitaev by exploiting the structure of optimal dual solutions. We also study a family of classical coin-flipping protocols based on classical bit-commitment. Cheating strategies for these classical protocols can be formulated as linear programs which are closely related to the semidefinite programs for the quantum version. In fact, we can construct point games for the classical protocols as well using the analysis for the quantum case. We discuss the philosophical connections between the classical and quantum protocols and their point games as viewed from optimization theory. In particular, we observe an analogy between a spectrum of physical theories (from classical to quantum) and a spectrum of convex optimization problems (from linear programming to semidefinite programming, through second-order cone programming). In this analogy, classical systems correspond to linear programming problems and the level of quantum features in the system is correlated to the level of sophistication of the semidefinite programming models on the optimization side. Concerning security analysis, we use the classical point games to prove that every classical protocol of this type allows exactly one of the parties to entirely determine the coin-flip. Using the intricate relationship between the semidefinite programming based quantum protocol analysis and the linear programming based classical protocol analysis, we show that only “classical” protocols can saturate Kitaev's lower bound for strong coin-flipping. Moreover, if the product of Alice and Bob's optimal cheating probabilities is 1/2, then exactly one party can perfectly control the outcome of the protocol. This rules out quantum protocols of this type from attaining the optimal level of security.
Citation
April 2015
Article
View Quantum and classical coin-flipping protocols based on bit-commitment and their point games