We introduce a primitive for quantum cryptography that we term ``state targeting.'' We show that increasing one's probability of success in this task above a minimum amount implies an unavoidable increase in the probability of a particular kind of failure. This is analogous to the unavoidable disturbance to a quantum state that results from gaining information about its identity, and can be shown to be a purely quantum effect. We solve various optimization problems for state targeting that are useful for the security analysis of two-party cryptographic tasks implemented between remote antagonistic parties. Although we focus on weak coin flipping, the results are significant for other two-party protocols, such as strong coin flipping, partially binding and concealing bit commitment, and bit escrow. Furthermore, the results have significance not only for the traditional notion of security in cryptography, that of restricting a cheater's ability to bias the outcome of the protocol, but also for a different notion of security that arises only in the quantum context, that of cheat sensitivity. Finally, our analysis leads to some interesting secondary results, namely, a generalization of Uhlmann's theorem and an operational interpretation of the fidelity between two mixed states.
We introduce a primitive for quantum cryptography that we term ``state targeting.'' We show that increasing one's probability of success in this task above a minimum amount implies an unavoidable increase in the probability of a particular kind of failure. This is analogous to the unavoidable disturbance to a quantum state that results from gaining information about its identity, and can be shown to be a purely quantum effect. We solve various optimization problems for state targeting that are useful for the security analysis of two-party cryptographic tasks implemented between remote antagonistic parties. Although we focus on weak coin flipping, the results are significant for other two-party protocols, such as strong coin flipping, partially binding and concealing bit commitment, and bit escrow. Furthermore, the results have significance not only for the traditional notion of security in cryptography, that of restricting a cheater's ability to bias the outcome of the protocol, but also for a different notion of security that arises only in the quantum context, that of cheat sensitivity. Finally, our analysis leads to some interesting secondary results, namely, a generalization of Uhlmann's theorem and an operational interpretation of the fidelity between two mixed states.
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.
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.
Coin flipping is a cryptographic primitive in which two spatially separated players, who in principle do not trust each other, wish to agree on a random bit. Classical and quantum coin flipping protocols have been studied extensively for more than twenty‐five years. However, until recently, quantum coin flipping protocols were designed without taking into consideration the losses of quantum information that would be unavoidable in any realistic implementation. We introduced in 2008 a novel protocol and proved its security even when losses are taken into account: no cheating player could obtain a desired outcome with a probability greater than (6+2)/8≈93%. Here, we refine our earlier protocol by making it fair in the sense that the optimal cheating strategies allow either player to bias the outcome by the same amount. Specifically, either player can cheat to obtain a desired outcome with probability exactly 90%, but no more. An implementation is underway.
Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We introduce a related new primitive - {\em quantum bit escrow}. In this primitive Alice commits to a bit b to Bob. The commitment is {\em binding} in the sense that if Alice is asked to reveal the bit, Alice can not bias her commitment without having a good probability of being detected cheating. The commitment is {\em sealing} in the sense that if Bob learns information about the encoded bit, then if later on he is asked to prove he was playing honestly, he is detected cheating with a good probability. Rigorously proving the correctness of quantum cryptographic protocols has proved to be a difficult task. We develop techniques to prove quantitative statements about the binding and sealing properties of the quantum bit escrow protocol.
A related primitive we construct is a quantum biased coin flipping protocol where no player can control the game, i.e., even an all-powerful cheating player must lose with some constant probability, which stands in sharp contrast to the classical world where such protocols are impossible.
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.
Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We introduce a related new primitive - {\em quantum bit escrow}. In this primitive Alice commits to a bit b to Bob. The commitment is {\em binding} in the sense that if Alice is asked to reveal the bit, Alice can not bias her commitment without having a good probability of being detected cheating. The commitment is {\em sealing} in the sense that if Bob learns information about the encoded bit, then if later on he is asked to prove he was playing honestly, he is detected cheating with a good probability. Rigorously proving the correctness of quantum cryptographic protocols has proved to be a difficult task. We develop techniques to prove quantitative statements about the binding and sealing properties of the quantum bit escrow protocol. A related primitive we construct is a quantum biased coin flipping protocol where no player can control the game, i.e., even an all-powerful cheating player must lose with some constant probability, which stands in sharp contrast to the classical world where such protocols are impossible.