Computing key rates for one-sided device-independent quantum key distribution
with Gereon Koßmann, Martin Sandfuchs, René Schwonnek, Giuseppe Viola, and Ramona Wolf
The defining feature of one-sided device-independent quantum key distribution is its asymmetric trust model in which one party trusts its devices and the other one does not. Examples include interactions between an ATM (trusted) and a customer’s smartphone (untrusted). This scenario sets an interesting middle ground between high key rates achievable by characterizing devices and the security of full device-independence. Here, we provide new tools, methods, and benchmarks for calculating key rates in this setting. To achieve this, we develop and compare two extensions of the NPA hierarchy and derive finite-size security bounds against general attacks with arbitrary device memory. The latter is based on the Generalized Entropy Accumulation Theorem. We then investigate the performance of various protocols: the BB84 protocol both with and without losses, a qutrit mutually unbiased bases protocol, and protocols based on Bell inequalties such as CHSH and I3322. We find that the choice of which party is characterized can strongly affects the key rate, surprisingly without a universal ordering. Our work thus offers a general toolbox for calculating key rates for one-sided device-independent QKD protocols. [arXiv]
Equivalence of non-local computation tasks beyond Clifford operations
with Simon Höfer, Alex May, Florian Speelman and Philip Verduyn Lunel
Non-local quantum computation (NLQC) studies how two collaborating players can implement channels on distributed systems using a single simultaneous round of quantum communication and shared entanglement. NLQC has applications in diverse areas, ranging from quantum position-verification to quantum gravity. Recently, it has been realized that the relationships among families of NLQC tasks are highly structured: many seemingly distinct tasks are related by reductions, wherein implementations of one task can be used to efficiently implement a second task. This is analogous to the notion of reduction in complexity theory, and reveals the relative hardness of NLQC tasks. In this work we continue the study of reductions among NLQC tasks. We focus on NLQC examples of the greatest interest in quantum position-verification; in particular examples involving large classical inputs and fixed-size quantum inputs, since these constitute the most feasible protocols for position-verification schemes. Within this setting, we find many new relationships among NLQC tasks. For instance, protocols for the simplest example of redirecting a quantum system based on a classical control imply protocols for controlled single qubit measurements in arbitrary bases, the controlled application of any Clifford unitary, and even the controlled application of any unitary of the form of an arbitrary diagonal unitary and sandwiched between two Clifford circuits. This implies that many feasible position-verification schemes have the same asymptotic scaling for their entanglement cost, and hence a similar level of security. Our techniques rely on ideas from gate teleportation and measurement based quantum computation, among other areas, bringing several new strategies into NLQC which may be of independent interest. [arXiv]
Device independent quantum key distribution with robust self-tests
with Gereon Koßmann and René Schwonnek
Device-independent quantum key distribution (DIQKD) provides a model of quantum key distribution with minimal assumptions and highly abstract theoretical building blocks. In particular, the parties do not need to trust that their quantum devices work as specified. Although DIQKD frees us from detailed discussions of specific device models and associated error parameters, it replaces them with fundamental assumptions about the validity of quantum experiments. In this work, we propose a way to lift a protocol based on DIQKD-style assumptions to a device-dependent QKD protocol (where the parties trust their quantum devices) by performing local self-tests in the laboratories of the two key-generating parties. In particular, we consider routed Bell-test setups as a means of self-testing the local parties in earnest and develop a rigorous mathematical framework showing that the underlying optimization problems can indeed be transferred to the device-dependent QKD setting. As an application, we illustrate many of the relevant techniques through the case study of a routed BB84 protocol. [arXiv]
A complexity theory for non-local quantum computation
with Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, and Henry Yuen
Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. They include attacks on quantum position verification (QPV) protocols as special cases. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that f-measure and f-route, attacks on the two most promising QPV protocols, are in fact equivalent under O(1) overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to f-measure. For instance, we obtain sub-exponential upper bounds on f-measure for all functions. Beyond this, we study a number of other examples of NLQC tasks and their relationships. [journal] [arXiv]
Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss
with Rene Allerstorfer, Harry Buhrman, Matthias Christandl, Llorenç Escolà-Farràs, Florian Speelman, and Philip Verduyn Lunel
A big challenge on the way towards practical protocols for secure quantum position-verification is the fact that in experimental setups e.g. using fiber optics, most of the photons sent get lost. That can compromise the security of protocols of interest. We prove that adding a commitment step, we can prove security for a large class of protocols against arbitrary photon loss, thereby exhibiting the first protocol that is both secure against photon loss, secure against entangled attackers, can allow the quantum information to travel slowly, and is simple for the honest parties. This makes the protocol an ideal candidate for experimental implementation. [journal] [arXiv]
A single-qubit position verification protocol that is secure against multi-qubit attacks
with Matthias Christandl and Florian Speelman
Imagine that you sit in front of a computer and look at a website that looks like the website of your bank. But how can you be sure that it is genuine? If you could verify that the server is indeed in the basement of the bank, you could stop worrying. This is the idea behind position-based cryptography: The position of a party is used as a credential. Unfortunately, secure position-verification, the fundamental building block of position-based cryptography, is classically impossible. However, quantum protocols for this task exist. We put forward the hitherto simplest such protocol and prove that it is secure as long as the attackers have at most an amount of qubits linear in the classical information sent during the protocol, while the honest parties only need a single qubit. Since classical bits are much easier to control than qubits, this makes the protocol secure in practice. [journal] [arXiv]