Code-routing: a new attack on position verification

Abstract

The cryptographic task of position verification attempts to verify one party's location in spacetime by exploiting constraints on quantum information and relativistic causality. A popular verification scheme known as $f$-routing involves requiring the prover to redirect a quantum system based on the value of a Boolean function $f$. Cheating strategies for the $f$-routing scheme require the prover use pre-shared entanglement, and security of the scheme rests on assumptions about how much entanglement a prover can manipulate. Here, we give a new cheating strategy in which the quantum system is encoded into a secret-sharing scheme, and the authorization structure of the secret-sharing scheme is exploited to direct the system appropriately. This strategy completes the $f$-routing task using $O(S{P}_p(f))$ EPR pairs, where $S{P}_p(f)$ is the minimal size of a span program over the field ${\mathbb{Z}}_p$ computing $f$. This shows we can efficiently attack $f$-routing schemes whenever $f$ is in the complexity class ${\text{Mod}}_p\text{L}$, after allowing for local pre-processing. The best earlier construction achieved the class L, which is believed to be strictly inside of ${\text{Mod}}_p\text{L}$. We also show that the size of a quantum secret sharing scheme with indicator function $f_I$ upper bounds entanglement cost of $f$-routing on the function $f_I$.

29 pages, v4 adds minor comments

References in corpus (3)

• Location-Dependent Communications using Quantum Entanglement
• Complexity and entanglement in non-local computation and holography
• A single-qubit position verification protocol that is secure against multi-qubit attacks

Cited by in corpus (6)

• Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers
• Continuous-variable Quantum Position Verification secure against entangled attackers
• Security of quantum position-verification limits Hamiltonian simulation via holography
• Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss
• Impossibility of perfect cheating for single-qubit position verification
• Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography