We present a new protocol and two lower bounds for quantum coin flipping. In our protocol, no dishonest party can achieve one outcome with probability more than 0.75. Then, we show that our protocol is optimal for a certain type of quantum protocols.
We present a new protocol and two lower bounds for quantum coin flipping. In our protocol, no dishonest party can achieve one outcome with probability more than 0.75. Then, we show that our protocol is optimal for a certain type of quantum protocols. For arbitrary quantum protocols, we show that if a protocol achieves a bias of at most ε, it must use at least Ω(loglogε1) rounds of communication. This implies that the parallel repetition fails for quantum coin flipping. (The bias of a protocol cannot be arbitrarily decreased by running several copies of it in parallel.)
We study the class of protocols for weak quantum coin flipping introduced by Spekkens and Rudolph (quant-ph/0202118). We show that, for any protocol in this class, one party can win the coin flip with probability at least 1/2.
We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) we propose and motivate a definition for quantum broadcast. Our model of quantum broadcast channel is new. (2) We discovered that quantum broadcast is essentially a combination of pairwise quantum channels and a classical broadcast channel. This is a somewhat surprising conclusion, but helps us in both our lower and upper bounds. (3) We provide tight upper and lower bounds on the optimal bias /spl epsiv/ of a coin which can be flipped by k parties of which exactly g parties are honest: for any 1 /spl les/ g /spl les/ k, /spl epsiv/ = 1/2 - /spl Theta/ (g/k). Thus, as long as a constant fraction of the players are honest, they can prevent the coin from being fixed with at least a constant probability. This result stands in sharp contrast with the classical setting, where no non-trivial coin-flipping is possible when g /spl les/ k/2.
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.