  


Quantum and classical coinflipping protocols based on bitcommitment and their point games
Ashwin Nayak(ashwin.nayakuwaterloo.ca) Abstract: We focus on a family of quantum coinflipping protocols based on quantum bitcommitment. 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 secondorder 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 coinflipping protocols based on classical bitcommitment. 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 secondorder 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 coinflip. 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 coinflipping. 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, coinflipping, semidefinite programming, secondorder cone programming, linear programming Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Linear, Cone and Semidefinite Programming (SecondOrder Cone Programming ) Category 3: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: April 2015 Download: [PDF] Entry Submitted: 04/21/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  