Each classical public-coin protocol for coin flipping is naturally associated with a quantum protocol for weak coin flipping. The quantum protocol is obtained by replacing classical randomness with quantum entanglement and by adding a cheat detection test in the last round that verifies the integrity of this entanglement. The set of such protocols defines a family which contains the protocol with bias 0.192 previously found by the author, as well as protocols with bias as low as $1∕6$ described herein. The family is analyzed by identifying a set of optimal protocols for every number of messages. In the end, tight lower bounds for the bias are obtained which prove that $1∕6$ is optimal for all protocols within the family.
Each classical public-coin protocol for coin flipping is naturally associated with a quantum protocol for weak coin flipping. The quantum protocol is obtained by replacing classical randomness with quantum entanglement and by adding a cheat detection test in the last round that verifies the integrity of this entanglement. The set of such protocols defines a family which contains the protocol with bias 0.192 previously found by the author, as well as protocols with bias as low as 1∕6 described herein. The family is analyzed by identifying a set of optimal protocols for every number of messages. In the end, tight lower bounds for the bias are obtained which prove that 1∕6 is optimal for all protocols within the family.
We present a family of protocols for flipping a coin over a telephone in a quantum mechanical setting. The family contains protocols with n + 2 messages for all n > 1, and asymptotically achieves a bias of 0.192. The case n = 2 is equivalent to the protocol of Spekkens and Rudolph with bias 0.207, which was the best known protocol. The case n = 3 achieves a bias of 0.199, and n = 8 achieves a bias of 0.193. The analysis of the protocols uses Kitaev's description of coin-flipping as a semidefinite program. We construct an analytical solution to the dual problem which provides an upper bound on the amount that a party can cheat.
In this paper, we focus on a special framework for quantum coin flipping protocols,_bit-commitment based protocols_, within which almost all known protocols fit. We show a lower bound of 1/16 for the bias in any such protocol. We also analyse a sequence of multi-round protocol that tries to overcome the drawbacks of the previously proposed protocols, in order to lower the bias. We show an intricate cheating strategy for this sequence, which leads to a bias of 1/4. This indicates that a bias of 1/4 might be optimal in such protocols, and also demonstrates that a cleverer proof technique may be required to show this optimality.
Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose Λ points (compared to 0 in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with Λ=0.01, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond 1/2+10−8, which uses 24 qubits and 1016 rounds of communication (provably 107 times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to 1/2+10−10) and reducing the rounds of communication (down to 25,180), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.
Quantum protocols for coin flipping can be composed in series in such a way that a cheating party gains no extra advantage from using entanglement between different rounds. This composition principle applies to coin-flipping protocols with cheat sensitivity as well, and is used to derive two results: There are no quantum strong coin-flipping protocols with cheat sensitivity that is linear in the bias (or bit-commitment protocols with linear cheat detection) because these can be composed to produce strong coin flipping with arbitrarily small bias. On the other hand, it appears that quadratic cheat detection cannot be composed in series to obtain even weak coin flipping with arbitrarily small bias.
Coin flipping is a fundamental cryptographic primitive that enables two distrustful and far apart parties to create a uniformly random bit. Quantum information allows for protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambain is achieved a cheating probability of at most 3/4. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2}. Closing this gap has been one of the important open questions in quantum cryptography. In this paper, we resolve this question by presenting a quantum strong coin flipping protocol with cheating probability arbitrarily close to 1/sqrt{2}.More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2+epsilon in order to achieve a strong coin flipping protocol with cheating probability 1/sqrt{2}+O(epsilon). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by Mochon.
Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than 1/2 [A. Kitaev, Presentation at the 6th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present a quantum strong coin flipping protocol with cheating probability arbitrarily close to 1/2. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2+ε in order to achieve a strong coin flipping protocol with cheating probability 1/2+O(ε). The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately γ≈0.739, improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to γ. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2+ε in order to achieve a quantum bit commitment protocol with cheating probability γ+O(ε). To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.