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.
It is well known that unconditionally secure bit commitment is impossible even in the quantum world. In this paper a weak variant of quantum bit commitment, introduced independently by Aharonov et al. [STOC, 2000] and Hardy and Kent [Phys. Rev. Lett. 92 (2004)] is investigated. In this variant, the parties require some nonzero probability of detecting a cheating, i.e. if Bob, who commits a bit b to Alice, changes his mind during the revealing phase then Alice detects the cheating with a positive probability (we call this property binding); and if Alice gains information about the committed bit before the revealing phase then Bob discovers this with positive probability (sealing). In our paper we give quantum bit commitment scheme that is simultaneously binding and sealing and we show that if a cheating gives epsilon advantage to a malicious Alice then Bob can detect the cheating with a probability Omega(epsilon^2). If Bob cheats then Alice's probability of detecting the cheating is greater than some fixed constant lambda>0. This improves the probabilities of cheating detections shown by Hardy and Kent and the scheme by Aharonov et al. who presented a protocol that is either binding or sealing, but not simultaneously both. To construct a cheat sensitive quantum bit commitment scheme we use a protocol for a weak quantum one-out-of-two oblivious transfer.
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.
We define
(varepsilon,delta)-secure quantum computations between two parties that can play dishonestly to maximise advantage
delta, however keeping small the probability
varepsilon that the computation fails in evaluating correct value. We present a simple quantum protocol for computing one-out-of-two oblivious transfer that is
(O(sqrtvarepsilon),varepsilon)-secure. Using the protocol as a black box we construct a scheme for cheat sensitive quantum bit commitment which guarantee that a mistrustful party has a nonzero probability of detecting a cheating.
Proof of security of cryptographic protocols theoretically establishes the strength of a protocol and the constraints under which it can perform, it does not take into account the overall design of the protocol. In the past model checking has been successfully applied to classical cryptographic protocols to weed out design flaws which would have otherwise gone unnoticed. Quantum cryptographic protocols differ from their classical counterparts, in their ability to detect the presence of an eavesdropper. Although unconditional security has been proven for both BB84 and B92 protocols, in this paper we show that identifying an eavesdropper's presence is constrained on the number of qubits exchanged. We first model the protocols in CQP and then explain the mechanism by which we have translated this into a PRISM model. We mainly focus on the protocols' ability to detect an active eavesdropper and the extent to which an eavesdropper can retrieve the shared key without being detected by either party. We then conclude by comparing the performance of the protocols.