Adversarial Two-Party Quantum Interactions in Cryptography and Machine Learning

Abstract

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.