The Impossibility of Efficient Quantum Weak Coin-Flipping

Abstract

How can two parties with competing interests carry out a fair coin flip, using only a noiseless quantum channel? This problem (quantum weak coin-flipping) was formalized more than 15 years ago, and, despite some phenomenal theoretical progress, practical quantum coin-flipping protocols with vanishing bias have proved hard to find. In the current work we show that there is a reason that practical weak quantum coin-flipping is difficult: any quantum weak coin-flipping protocol with bias $\epsilon$ must use at least $\exp (\Omega (1/\sqrt{\epsilon }))$ rounds of communication. This is a large improvement over the previous best known lower bound of $\Omega (\log \log (1/\epsilon ))$ due to Ambainis from 2004. Our proof is based on a theoretical construction (the two-variable profile function) which may find further applications.

arXiv commentAdded a diagram (Figure 5) and some explanatory text to the paper. Minor corrections and clarifications. 24 pages

References in corpus (11)

• Unconditionally secure quantum bit commitment is impossible
• Is Quantum Bit Commitment Really Possible?
• Insecurity of Quantum Secure Computations
• Quantum Cryptography Beyond Quantum Key Distribution
• Degrees of concealment and bindingness in quantum bit commitment protocols
• A quantum protocol for cheat-sensitive weak coin flipping
• Complete Insecurity of Quantum Protocols for Classical Two-Party Computation
• Quantum weak coin flipping with arbitrarily small bias
• Multiparty Quantum Coin Flipping
• A large family of quantum weak coin-flipping protocols
• Quantum Weak Coin Flipping

Cited by in corpus (6)

• Privacy and correctness trade-offs for information-theoretically secure quantum homomorphic encryption
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• On the composable security of weak coin flipping
• Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games
• Experimental cheat-sensitive quantum weak coin flipping