Quantum Weak Coin Flipping

Abstract

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. For weak coin flipping the players have known opposite preferred values. A weak coin-flipping protocol has a bias $\epsilon$ if neither player can force the outcome towards their preferred value with probability more than $\frac{1}{2}+\epsilon$. While it is known that all classical protocols have $\epsilon =\frac{1}{2}$, Mochon showed in 2007 [arXiv:0711.4114] that quantumly weak coin flipping can be achieved with arbitrarily small bias (near perfect) but the best known explicit protocol has bias $1/6$ (also due to Mochon, 2005 [Phys. Rev. A 72, 022341]). We propose a framework to construct new explicit protocols achieving biases below $1/6$. In particular, we construct explicit unitaries for protocols with bias approaching $1/10$. To go below, we introduce what we call the Elliptic Monotone Align (EMA) algorithm which, together with the framework, allows us to numerically construct protocols with arbitrarily small biases.

arXiv comment98 pages split into 3 parts, 10 figures; For updates and contact information see https://atulsingharora.github.io/WCF. Version 2 has minor improvements. arXiv admin note: text overlap with arXiv:1402.7166 by other authors

References in corpus (4)

• On bit-commitment based quantum coin flipping
• A large family of quantum weak coin-flipping protocols
• Quantum dice rolling: A multi-outcome generalization of quantum coin flipping
• A search for quantum coin-flipping protocols using optimization techniques

Cited by in corpus (5)

• Qubit teleportation between non-neighboring nodes in a quantum network
• The Impossibility of Efficient Quantum Weak Coin-Flipping
• On the composable security of weak coin flipping
• Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming
• Quantum Universally Composable Oblivious Linear Evaluation