Position-Based Quantum Cryptography: Impossibility and Constructions

Abstract

In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, no secure position-verification is possible at all. We show a distributed protocol for computing any unitary operation on a state shared between the different users, using local operations and one round of classical communication. Using this surprising result, we break any position-verification scheme of a very general form. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any pre-shared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.

27 pages, 5 figures. v4: improved proofs for the impossibility theorem and for the instantaneous computation theorem

References in corpus (9)

• Conjectured Strong Complementary Information Tradeoff
• Asymptotic teleportation scheme as a universal programmable quantum processor
• Simplified instantaneous non-local quantum computation with applications to position-based cryptography
• Quantum teleportation scheme by selecting one of multiple output ports
• Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints
• Location-Dependent Communications using Quantum Entanglement
• Insecurity of position-based quantum cryptography protocols against entanglement attacks
• Quantum Tasks in Minkowski Space
• Quantum Tagging for Tags Containing Secret Classical Data

Cited by in corpus (50)

• Advances in Quantum Cryptography
• Practical challenges in quantum key distribution
• Security in Quantum Cryptography
• Quantum Cryptography Beyond Quantum Key Distribution
• Device-Independent Relativistic Quantum Bit Commitment
• Spacetime-constrained oblivious transfer
• Asymptotic performance of port-based teleportation
• Complexity and entanglement in non-local computation and holography
• Device-independence for two-party cryptography and position verification
• Loss-tolerant position-based quantum cryptography
• A single-qubit position verification protocol that is secure against multi-qubit attacks
• Measurements of nonlocal variables and demonstration of the failure of the product rule for a pre- and postselected pair of photons
• Multiphoton and side-channel attacks in mistrustful quantum cryptography
• The connected wedge theorem and its consequences
• Quantum tasks in holography
• Quantum cryptography beyond key distribution: theory and experiment
• Practical Quantum Retrieval Games
• Bounds on Instantaneous Nonlocal Quantum Computation
• S-money: virtual tokens for a relativistic economy
• Optimal amount of entanglement to distinguish quantum states instantaneously
• Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation
• Relating non-local quantum computation to information theoretic cryptography
• Loss-tolerant quantum secure positioning with weak laser sources
• Transmission of quantum information through quantum fields in curved spacetimes
• Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers
• Holographic scattering and non-minimal RT surfaces
• Implementation of bipartite or remote unitary gates with repeater nodes
• Unconstrained Summoning for relativistic quantum information processing
• Relativistic (or $2$-prover $1$-round) zero-knowledge protocol for $\mathsf{NP}$ secure against quantum adversaries
• Free-space reconfigurable quantum key distribution network
• Code-routing: a new attack on position verification
• Classification of joint quantum measurements based on entanglement cost of localization
• Practically secure quantum position verification
• The Unruh-DeWitt model and its joint interacting Hilbert space
• Horizon causality from holographic scattering in asymptotically dS${}_3$
• Repeater-Based Quantum Communication Protocol: Maximizing Teleportation Fidelity with Minimal Entanglement
• QuTracer: Mitigating Quantum Gate and Measurement Errors by Tracing Subsets of Qubits
• Linear gate bounds against natural functions for position-verification
• Security of quantum position-verification limits Hamiltonian simulation via holography
• Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss
• Continuous-variable Quantum Position Verification secure against entangled attackers
• Distributing bipartite quantum systems under timing constraints
• Orthogonality Broadcasting and Quantum Position Verification
• Conditional disclosure of secrets with quantum resources
• Security Framework for Quantum Distance-Bounding
• Comparing Singlet Testing Schemes
• Impossibility of perfect cheating for single-qubit position verification
• Robust Relativistic Bit Commitment
• Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography
• A decompositional framework for process theories in spacetime