Die-rolling is the cryptographic task where two mistrustful, remote parties wish to generate a random D-sided die-roll over a communication channel. Optimal quantum protocols for this task have been given by Aharon and Silman (New Journal of Physics, 2010) but are based on optimal weak coin-flipping protocols that are currently very complicated and not very well understood. In this paper, we first present very simple classical protocols for die-rolling that have decent (and sometimes optimal) security, which is in stark contrast to coin-flipping, bit-commitment, oblivious transfer, and many other two-party cryptographic primitives. We also present quantum protocols based on the idea of integer-commitment, a generalization of bit-commitment, where one wishes to commit to an integer. We analyze these protocols using semidefinite programming and finally give protocols that are very close to Kitaev’s lower bound for any D ≥ 3 . Lastly, we briefly discuss an application of this work to the quantum state discrimination problem.
Die-rolling is the cryptographic task where two mistrustful, remote parties wish to generate a random D-sided die-roll over a communication channel. Optimal quantum protocols for this task have been given by Aharon and Silman (New Journal of Physics, 2010) but are based on optimal weak coin-flipping protocols that are currently very complicated and not very well understood. In this paper, we first present very simple classical protocols for die-rolling that have decent (and sometimes optimal) security, which is in stark contrast to coin-flipping, bit-commitment, oblivious transfer, and many other two-party cryptographic primitives. We also present quantum protocols based on the idea of integer-commitment, a generalization of bit-commitment, where one wishes to commit to an integer. We analyze these protocols using semidefinite programming and finally give protocols that are very close to Kitaev’s lower bound for any D ≥ 3 . Lastly, we briefly discuss an application of this work to the quantum state discrimination problem.
Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis 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/√2 (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important open question. In this paper, we provide the optimal bound for quantum bit commitment. First, we show a lower bound of approximately 0.739, improving Kitaev's lower bound. For this, we present some generic cheating strategies for Alice and Bob and conclude by proving a new relation between the trace distance and fidelity of two quantum states. Second, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to 0.739. 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 0.739 + O(ε). We then use the optimal quantum weak coin flipping protocol described by Mochon. Last, in order to stress the fact that our protocol uses quantum effects beyond the weak coin flip, we show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.
Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4[Amb01]. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2} [Kit03] (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important and open question. In this paper, we provide the optimal bound for quantum bit commitment. We first show a lower bound of approximately 0.739, improving Kitaev's lower bound. We then present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to 0.739. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + eps in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(eps). We then use the optimal quantum weak coin flipping protocol described by Mochon[Moc07]. To stress the fact that our protocol uses quantum effects beyond the weak coin flip, we 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 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 the cryptographic task of generating a random coin-flip between two mistrustful parties. Kitaev discovered that the security of quantum coin-flipping protocols can be analyzed using semidefinite programming. This lead to his result that one party can force a desired coin-flip outcome with probability at least 1/√2. \n \nWe give sufficient background in quantum computing and semidefinite programming to understand Kitaev's semidefinite programming formulation for coin-flipping cheating strategies. These ideas are specialized to a specific class of protocols singled out by Nayak and Shor. We also use semidefinite programming to solve for the maximum cheating probability of a particular protocol which has the best known security. \n \nFurthermore, we present a family of protocols where one party has a greater probability of forcing an outcome of 0 than an outcome of 1. We also discuss a computer search to find specific protocols which minimize the maximum cheating probability.
This thesis concerns the analysis of the unconditional security of quantum cryptographic protocols using convex optimization techniques. It is divided into the study of coin-flipping and oblivious transfer. We first examine a family of coin-flipping protocols. Almost all of the handful of explicitly described coin-flipping protocols are based on bit-commitment. To explore the possibility of finding explicit optimal or near-optimal protocols, we focus on a class which generalizes such protocols. We call these BCCF-protocols, for bit-commitment based coin-flipping. We use the semidefinite programming (SDP) formulation of cheating strategies along the lines of Kitaev to analyze the structure of the protocols. \n \nIn the first part of the thesis, we show how these semidefinite programs can be used to simplify the analysis of the protocol. In particular, we show that a particular set of cheating strategies contains an optimal strategy. This reduces the problem to optimizing a linear combination of fidelity functions over a polytope which has several benefits. First, it allows one to model cheating probabilities using a simpler class of optimization problems known as second-order cone programs (SOCPs). Second, it helps with the construction of point games due to Kitaev as described in Mochon's work. \nPoint games were developed to give a new perspective for studying quantum protocols. In some sense, the notion of point games is dual to the notion of protocols. \n \nThere has been increased research activity in optimization concerning generalizing theory and algorithms for linear programming to much wider classes of optimization problems such as semidefinite programming. For example, semidefinite programming provides a tool for potentially improving results based on linear programming or investigating old problems that have eluded analysis by linear programming. In this sense, the history of semidefinite programming is very similar to the history of quantum computation. \nQuantum computing gives a generalized model of computation to tackle new and old problems, improving on and generalizing older classical techniques. Indeed, there are striking differences between linear programming and semidefinite programming as there are between classical and quantum computation. In this thesis, we strengthen this analogy by studying a family of classical coin-flipping protocols based on classical bit-commitment. Cheating strategies for these ``classical BCCF-protocols'' can be formulated as linear programs (LPs) which are closely related to the semidefinite programs for the quantum version. In fact, we can construct point games for the classical protocols as well using the analysis for the quantum case. \n \nUsing point games, we prove that every classical BCCF-protocol allows exactly one of the parties to entirely determine the outcome. Also, we rederive Kitaev's lower bound to show that only ``classical'' protocols can saturate Kitaev's analysis. Moreover, if the product of Alice and Bob's optimal cheating probabilities is 1/2, then at least one party can cheat with probability 1. \n \nThe second part concerns the design of an algorithm to search for BCCF-protocols with small bias. Most coin-flipping protocols with more than three rounds have eluded direct analysis. To better understand the properties of optimal BCCF-protocols with four or more rounds, we turn to computational experiments. We design a computational optimization approach to search for the best protocol based on the semidefinite programming formulations of cheating strategies. We create a protocol filter using cheating strategies, some of which build upon known strategies and others are based on convex optimization and linear algebra. The protocol filter efficiently eliminates candidate protocols with too high a bias. Using this protocol filter and symmetry arguments, we perform searches in a matter of days that would have otherwise taken millions of years. Our experiments checked 1016 four and six-round BCCF-protocols and suggest that the optimal bias is 1/4. \n \nThe third part examines the relationship between oblivious transfer, bit-commitment, and coin-flipping. We consider oblivious transfer which succeeds with probability 1 when the two parties are honest and construct a simple protocol with security provably better than any classical protocol. We also derive a lower bound by constructing a bit-commitment protocol from an oblivious transfer protocol. Known lower bounds for bit-commitment then lead to a constant lower bound on the bias of oblivious transfer. Finally, we show that it is possible to use Kitaev's semidefinite programming formulation of cheating strategies to obtain optimal lower bounds on a ``forcing'' variant of oblivious transfer related to coin-flipping.
In the last two decades, there has been much effort in finding secure protocols for two-party cryptographic tasks. It has since been discovered that even with quantum mechanics, many such protocols are limited in their security promises. In this work, we use stochastic selection, an idea from stochastic programming, to circumvent such limitations. For example, we find a way to switch between bit commitment, weak coin flipping, and oblivious transfer protocols to improve their security. We also use stochastic selection to turn trash into treasure yielding the first quantum protocol for Rabin oblivious transfer.