QIP2021 | Device-independent protocols from computational assumptions (Tony Metger)

Authors: Tony Metger, Yfke Dulek, Andrea Coladangelo, Rotem Arnon-Friedman and Thomas Vidick Affiliations: ETH Zurich | QuSoft, University of Amsterdam | UC Berkeley | Weizmann Institute of Science | Caltech 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. Get entangled with us! ▶ QIP2021 Conference: https://www.mcqst.de​/qip2021​​ ▶ Website: https://www.mcqst.de​​​ ▶ Twitter: https://twitter.com/MCQST_cluster​​​ ▶ LinkedIn: https://www.linkedin.com/company/mcqst