  


A search for quantum coinflipping protocols using optimization techniques
Ashwin Nayak (anayakuwaterloo.ca) Abstract: Coinflipping is a cryptographic task in which two physically separated, mistrustful parties wish to generate a fair coinflip by communicating with each other. Chailloux and Kerenidis (2009) designed quantum protocols that guarantee coinflips with near optimal bias away from uniform, even when one party deviates arbitrarily from the protocol. The probability of any outcome in these protocols is provably at most $1/\sqrt{2} + \delta$ for any given $\delta$ > 0. However, no explicit description of these protocols is known, and the number of rounds in the protocols tends to infinity as $\delta$ goes to 0. In fact, the smallest bias achieved by known explicit protocols is 1/4 (Ambainis, 2001). We take a computational optimization approach, based mostly on convex optimization, to the search for simple and explicit quantum strong coinflipping protocols. We present a search algorithm to identify protocols with low bias within a natural class, protocols based on bitcommitment (Nayak and Shor, 2003). To make this search computationally feasible, we further restrict to commitment states used by Mochon (2005). An analysis of the resulting protocols via semidefinite programs (SDPs) unveils a simple structure. For example, we show that the SDPs reduce to secondorder cone programs. We devise novel cheating strategies in the protocol by restricting the semidefinite programs and use the strategies to prune the search. The techniques we develop enable a computational search for protocols given by a mesh over the corresponding parameter space. The protocols have up to six rounds of communication, with messages of varying dimension and include the best known explicit protocol (with bias 1/4). We conduct two kinds of search: one for protocols with bias below 0.2499, and one for protocols in the neighbourhood of protocols with bias 1/4. Neither of these searches yields better bias. Based on the mathematical ideas behind the search algorithm, we prove a lower bound of 0.2487 on the bias of a class of fourround protocols. Keywords: Quantum cryptography, semidefinite programming, computational optimization Category 1: Linear, Cone and Semidefinite Programming Category 2: Global Optimization (Applications ) Category 3: Optimization Software and Modeling Systems (Optimization Software Design Principles ) Citation: Download: [PDF] Entry Submitted: 03/04/2014 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  