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.

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.

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.

Sources producing high amounts of entanglement are essential for quantum cryptography. Given an uncharacterized source, manufactured by a possibly untrusted entity, how can we certify that it produces a lot of entanglement? We initiate the study of operational device-independent entanglement certification by presenting a device-independent protocol that lower-bounds the one-shot distillable entanglement of the remaining quantum state after the execution of the protocol. By this, the protocol certifies the amount of “useful entanglement” available for proceeding applications. Importantly, our protocol does not abort, with high probability, when testing realistically noisy sources.

Device-independent cryptography goes beyond conventional quantum cryptography by providing security that holds independently of the quality of the physical devices used to implement the cryptographic protocols. In this tutorial we will present existing device-independent quantum key distribution protocols and discuss the ideas underlying their security proofs. In particular, the tutorial will cover the best practices for using known techniques to prove security of device-independent protocols. Lastly, we will present several open questions whose solutions have the potential of bringing the quantum cryptography community closer to an experimental realization of device-independent quantum key distribution.

The ability to reduce proofs of quantum information processing tasks from any permutation in-variant state to a de-Finetti state, that is, a convex combination of i.i.d. states, is useful in several tasks, such as cryptographic quantum protocols and quantum tomography. It is thus interesting to see whether such de-Finetti type theorems are unique for quantum theory or can be proven for more general theories. We prove that this can indeed be done under the framework of conditional probability distributions. That is, a physical system is described by a conditional probability distribution PA|X where X denotes the possible measurements and A the possible outcomes. For such systems we prove a post selection theorem which states that any permutation invariant system PA|X can be post selected by a measurement of a de-Finetti type system with high enough probability. We use this theorem to simplify security proofs of non-signalling cryptographic protocols.