Optimization Online


Quantum and classical coin-flipping protocols based on bit-commitment and their point games

Ashwin Nayak(ashwin.nayak***at***uwaterloo.ca)
Jamie Sikora(cqtjwjs***at***nus.edu.sg)
Levent Tunçel(ltuncel***at***uwaterloo.ca)

Abstract: 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.

Keywords: Quantum cryptography, coin-flipping, semidefinite programming, second-order cone programming, linear programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: April 2015

Download: [PDF]

Entry Submitted: 04/21/2015
Entry Accepted: 04/22/2015
Entry Last Modified: 04/21/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society