Rotem Arnon-Friedman

In device-independent (DI) quantum protocols, the security statements are oblivious to the characterization of the quantum apparatus– they are based solely on the classical interaction with the devices as well as some well-defined assumptions. The most commonly known setup is the so-called non-local one, in which two devices that cannot communicate with each other present a violation of a Bell inequality. In recent years, a new variant of DI protocols, requiring only a single device, arose. In this novel research avenue, the no-communication assumption is replaced with a computational assumption which states that the device cannot solve certain post-quantum cryptographic tasks. The protocols in literature that have been analyzed in this setting, e.g., randomness certification, used ad hoc proof techniques. In addition, the strength of the achieved results is hard to judge due to their complexity. Here, we build on ideas coming from the study of non-local DI protocols and develop a new modular proof technique for the single-device computational setting. We present a flexible framework for proving the security of such protocols by utilizing a combination of tools from quantum information theory, such as the entropic uncertainty relation and the entropy accumulation theorem. This leads to an insightful and simple proof of security as well as to explicit quantitative bounds. Our work thus acts as the basis for the analysis of future protocols for DI randomness generation, expansion, amplification, and key distribution based on post-quantum cryptographic assumptions.

Abstract Device-independent protocols use untrusted quantum devices to achieve a cryptographic task. Such protocols are typically based on Bell inequalities and require the assumption that the quantum device is composed of separated non-communicating components. In this submission, we present protocols for self-testing and device-independent quantum key distribution (DIQKD) that are secure even if the components of the quantum device can exchange arbitrary quantum communication. Instead, we assume that the device cannot break a standard post-quantum cryptographic assumption. Importantly, the computational assumption only needs to hold during the protocol execution and only applies to the (adversarially prepared) device in possession of the (classical) user, while the adversary herself remains unbounded. The output of the protocol, e.g. secret keys in the case of DIQKD, is information-theoretically secure. For our self-testing protocol, we build on a recently introduced cryptographic tool (Brakerski et al., FOCS 2018; Mahadev, FOCS 2018) to show that a classical user can enforce a bipartite structure on the Hilbert space of a black-box quantum device, and certify that the device has prepared and measured a state that is entangled with respect to this bipartite structure. Using our self-testing protocol as a building block, we construct a protocol for DIQKD that leverages the computational assumption to produce information-theoretically secure keys. The security proof of our DIQKD protocol uses the self-testing theorem in a black-box way. Our self-testing theorem thus also serves as a first step towards a more general translation procedure for standard device-independent protocols to the setting of computationally bounded (but freely communicating) devices.