A search for quantum coin-flipping protocols using optimization techniques
From MaRDI portal
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. The probability of any outcome in these protocols is provably at most for any given . However, no explicit description of these protocols is known, and the number of rounds in the protocols tends to infinity as goes to 0. In fact, the smallest bias achieved by known explicit protocols is (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) restricting 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 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 on the bias of a class of four-round protocols.
Recommendations
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3825698 (Why is no real title available?)
- A new protocol and lower bounds for quantum coin flipping
- A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Implementation of interior point methods for mixed semidefinite and second order cone optimization problems
- Optimal Bounds for Quantum Bit Commitment
- Optimal Quantum Strong Coin Flipping
- Optimal counterfeiting attacks and generalizations for Wiesner's quantum money
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Complexity Theory
- Quantum bit escrow
- Quantum cryptography: public key distribution and coin tossing
- Strong duality and minimal representations for cone optimization
- Towards a general theory of quantum games
- Unconditional security in quantum cryptography
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Weak coin flipping with small bias
Cited in
(5)- A new protocol and lower bounds for quantum coin flipping
- Simple, near-optimal quantum protocols for die-rolling
- Fidelity of quantum strategies with applications to cryptography
- Optimized search for complex protocols based on entanglement detection
- scientific article; zbMATH DE number 5595866 (Why is no real title available?)
This page was built for publication: A search for quantum coin-flipping protocols using optimization techniques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263220)
