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.
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.
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.
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.
Two-party adversarial interactions are of fundamental importance in the study of cryptography and machine learning, as they allow us to work in dynamic environments to model and adapt to various challenges, fostering reliability and robustness. In this thesis, we first consider such interactions in the domain of information-theoretic cryptography, where we propose new protocols and security bounds involving various two-party primitives such as coin flipping, bit commitment, and variants of oblivious transfer. We begin by developing the mathematical framework of stochastic selection, which is potentially useful for devising new protocols with improved security for a combination of various tasks. We then use this idea to develop the first protocols for Rabin oblivious transfer that offer partial information-theoretic security and also provide a non-trivial lower bound on its security. We also relax some of the more commonly used assumptions to consider the security of protocols in broader compositions and independently, allowing for devices that may be potentially malicious. In the former setting, we demonstrate that the weak coin flipping task -- which enjoys almost perfect standalone security -- may not be immune to attacks when used in larger compositions. In the latter, we establish the impossibility of determining the inner workings of a shared quantum mechanical device -- a phenomenon commonly known as self-testing -- in the presence of an adversary. Finally, we consider a slightly different task in a similar setting, where we discuss the classical online learnability of various quantum objects. We prove a sublinear regret bound for learning over general subsets of positive semidefinite matrices via the regularized follow-the-leader algorithm and apply it to various settings involving the learning of quantum objects. For concrete applications, we present a sublinear regret bound for learning quantum states, effects, channels, interactive measurements, strategies, co-strategies, and collections of inner products of pure states. In proving our regret bound, we establish various matrix analysis results useful in quantum information theory, including a generalization of Pinsker's inequality for arbitrary positive semidefinite operators with possibly different traces, which may be of independent interest in the study of more general classes of divergences.
A significant branch of classical cryptography deals with the problems which arise when mistrustful parties need to generate, process, or exchange information. As Kilian showed a while ago, mistrustful classical cryptography can be founded on a single protocol, oblivious transfer, from which general secure multiparty computations can be built. The scope of mistrustful quantum cryptography is limited by no-go theorems, which rule out, inter alia, unconditionally secure quantum protocols for oblivious transfer or general secure two-party computations. These theorems apply even to protocols which take relativistic signaling constraints into account. The best that can be hoped for, in general, are quantum protocols which are computationally secure against quantum attack. Here a method is described for building a classically certified bit commitment, and hence every other mistrustful cryptographic task, from a secure coin-tossing protocol. No security proof is attempted, but reasons are sketched why these protocols might resist quantum computational attack.
A significant branch of classical cryptography deals with the problems which arise when mistrustful parties need to generate, process or exchange information. As Kilian showed a while ago, mistrustful classical cryptography can be founded on a single protocol, oblivious transfer, from which general secure multi-party computations can be built. The scope of mistrustful quantum cryptography is limited by no-go theorems, which rule out, inter alia, unconditionally secure quantum protocols for oblivious transfer or general secure two-party computations. These theorems apply even to protocols which take relativistic signalling constraints into account. The best that can be hoped for, in general, are quantum protocols computationally secure against quantum attack. I describe here a method for building a classically certified bit commitment, and hence every other mistrustful cryptographic task, from a secure coin tossing protocol. No security proof is attempted, but I sketch reasons why these protocols might resist quantum computational attack.
Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest players' cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than 1/2. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a coin flipping protocol and conclude by using Kitaev's coin flipping lower bound. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most 3/4. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.