-

 

 

 




Optimization Online





 

A search for quantum coin-flipping protocols using optimization techniques

Ashwin Nayak (anayak***at***uwaterloo.ca)
Jamie Sikora (Jamie.Sikora***at***liafa.univ-paris-diderot.fr)
Levent Tunšel (ltuncel***at***uwaterloo.ca)

Abstract: Coin-flipping is a cryptographic task in which two physically separated, mistrustful parties wish to generate a fair coin-flip by communicating with each other. Chailloux and Kerenidis (2009) designed quantum protocols that guarantee coin-flips 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 coin-flipping protocols. We present a search algorithm to identify protocols with low bias within a natural class, protocols based on bit-commitment (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 second-order 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 four-round 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
Entry Accepted: 03/04/2014
Entry Last Modified: 09/11/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
Mathematical Optimization Society