The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, Physical Review A, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers. Our techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length.
We show that, for input length $n$ and a sufficiently small constant $ε>0$, a uniform strategy running in time $T$ and succeeding with probability at least $1-ε$ on every input implies the following computational bounds on $f$.
1. If the strategies are arbitrary quantum channels, then $f\in \mathrm{QSZK}(\mathrm{poly}(T))$, where $\mathrm{QSZK}(T)$ is the class of languages having quantum statistical zero-knowledge proofs in which the verifier runs in time $T$ and the simulator in time $\mathrm{poly}(T)$.
2. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in \mathrm{DTIME}(\mathrm{poly}(T2^t))$.
3. If the strategies are explicit Pauli-sparse unitaries acting on at most $T$ qubits and having at most $s$ nonzero Pauli coefficients, then $f\in \mathrm{DTIME}(\mathrm{poly}(Ts))$.
Time and space hierarchies then yield explicit functions secure against superlinear and even all polynomial-time adversaries under our computational restrictions. These bounds exceed the bounded-storage qubit bound $q\leq\log n$ of Bluhm, Christandl, and Speelman (Nature Physics, 2022) for the inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.
AI Summary
The paper studies computational resource lower bounds for attacks on $f$-routing, a candidate protocol for quantum position verification. It asks whether restricting adversarial computation can yield security guarantees for explicit functions beyond those obtained from communication-complexity arguments, which provide at most linear bounds in the input length.
For input length $n$ and sufficiently small constant $\varepsilon>0$, the results relate a uniform attack running in time $T$ and succeeding with probability at least $1-\varepsilon$ on every input to the complexity of computing $f$. Arbitrary quantum-channel attacks imply $f\in\mathrm{QSZK}(\mathrm{poly}(T))$, with polynomially bounded verifier and simulator runtimes. Clifford+$T$ attacks using at most $t$ magic gates imply $f\in\mathrm{DTIME}(\mathrm{poly}(T2^t))$. Attacks implemented by explicit Pauli-sparse unitaries on at most $T$ qubits, with at most $s$ nonzero Pauli coefficients, imply $f\in\mathrm{DTIME}(\mathrm{poly}(Ts))$.
These complexity containments, combined with time and space hierarchy theorems, yield explicit functions secure against superlinear and even all polynomial-time adversaries within the specified models. The supplied text contains only the abstract and LaTeX front matter, so the reductions establishing the containments cannot be described in detail.
The stated trade-offs are restrictions to uniform, computationally bounded adversaries and increased honest evaluation complexity. The guarantees concern attacks achieving high success on every input. The comparison with the earlier $q\leq\log n$ bounded-storage guarantee for inner product therefore changes both the adversarial model and the cost of evaluating the routing function.
No sign of AI-generated textStrong assumptions
Central claim may not hold: The supplied manuscript contains only an abstract and a LaTeX preamble, so it does not establish any of the claimed computational bounds or their hierarchy-based security consequences.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
The f-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, Physical Review A, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers. Our techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length.
We show that, for input length n and a sufficiently small constant ε>0, a uniform strategy running in time T and succeeding with probability at least 1−ε on every input implies the following computational bounds on f.
If the strategies are arbitrary quantum channels, then f∈QSZK(poly(T)), where QSZK(T) is the class of languages having quantum statistical zero-knowledge proofs in which the verifier runs in time T and the simulator in time poly(T).
If the strategies are Clifford+T circuits using at most t magic gates, then f∈DTIME(poly(T2t)).
If the strategies are explicit Pauli-sparse unitaries acting on at most T qubits and having at most s nonzero Pauli coefficients, then f∈DTIME(poly(Ts)).
Time and space hierarchies then yield explicit functions secure against superlinear and even all polynomial-time adversaries under our computational restrictions. These bounds exceed the bounded-storage qubit bound q≤logn of Bluhm, Christandl, and Speelman (Nature Physics, 2022) for the inner product function f=IP, at the cost of restricting adversarial computation and increasing honest evaluation complexity.
The paper studies computational resource lower bounds for attacks on f-routing, a candidate protocol for quantum position verification. It asks whether restricting adversarial computation can yield security guarantees for explicit functions beyond those obtained from communication-complexity arguments, which provide at most linear bounds in the input length.
For input length n and sufficiently small constant ε>0, the results relate a uniform attack running in time T and succeeding with probability at least 1−ε on every input to the complexity of computing f. Arbitrary quantum-channel attacks imply f∈QSZK(poly(T)), with polynomially bounded verifier and simulator runtimes. Clifford+T attacks using at most t magic gates imply f∈DTIME(poly(T2t)). Attacks implemented by explicit Pauli-sparse unitaries on at most T qubits, with at most s nonzero Pauli coefficients, imply f∈DTIME(poly(Ts)).
These complexity containments, combined with time and space hierarchy theorems, yield explicit functions secure against superlinear and even all polynomial-time adversaries within the specified models. The supplied text contains only the abstract and LaTeX front matter, so the reductions establishing the containments cannot be described in detail.
The stated trade-offs are restrictions to uniform, computationally bounded adversaries and increased honest evaluation complexity. The guarantees concern attacks achieving high success on every input. The comparison with the earlier q≤logn bounded-storage guarantee for inner product therefore changes both the adversarial model and the cost of evaluating the routing function.
A quantum position-verification scheme attempts to verify the spatial location of a prover. The prover is issued a challenge with quantum and classical inputs and must respond with appropriate timings. We consider two well-studied position-verification schemes known as f -routing and f -BB84. Both schemes require an honest prover to locally compute a classical function f of inputs of length n , and manipulate O(1) size quantum systems. We prove the number of quantum gates plus single qubit measurements needed to implement a function f is lower bounded linearly by the communication complexity of f in the simultaneous message passing model with shared entanglement. Taking f(x,y)=∑ixiyi to be the inner product function, we obtain a Ω(n) lower bound on quantum gates plus single qubit measurements. The scheme is feasible for a prover with linear classical resources and O(1) quantum resources, and secure against sub-linear quantum resources.
New lower bounds for CDS and f-routing
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is f-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC.
Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and f-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function.
Second, we consider one-sided-perfect f-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.
The goal of position-based cryptography is for an honest party to use her spatio-temporal position as her only credential in a cryptographic protocol. In particular, Position-Verification aims at verifying that a certain party, called the prover, holds a given position in spacetime. Such a protocol typically goes as follows: a set of verifiers will coordinate and send some challenge to the prover, and it is expected that only someone sitting in the supposed position of the prover can successfully pass the challenge. Two papers established that information theoretic security is not possible for Position-Based Quantum Cryptography (PBQC) protocols: neither in the classical [1], nor in the quantum [2] regime. More precisely, it is always possible for a coalition of adversaries to convince the verifiers, even if none of the adversary sits in the spatiotemporal region where the prover is supposed to be. At the same time, the best known attack strategies require the adversaries to share very entangled states: the attacks described in [2] are based on Vaidman’s protocol for nonlocal computation [3] and consist in the cheaters teleporting some quantum state back and forth, with a total cost in terms of required EPR pairs that scales double exponentially in n, the number of qubits involved in the PBQC protocol. Later, new generic attacks based on port-based teleportation[4] were proposed and require only exponential entanglement to succeed [5]. Finally, it is also know that a linear amount of entanglement is not su cient to break the PBQC protocol [5], [6]. A major open question in the field is to bridge the gap between lower and upper bounds: does there exist a protocol that requires exponentially many EPR pairs to break, or are all PBQC protocols insecure against a coalition of adversaries that shares polynomially many EPR pairs? While we do not settle this question in the present paper, we make some progress towards it by exhibiting new attack strategies with polynomial complexity against a large family of practical protocols. These attacks rely on teleportation gates and their precise complexity can be quantified with the notion of Cli↵ord hierarchy [7] of a quantum gate. We then introduce a new family of protocols, that generalizes a construction by Lau and Lo [8], which appears to be immune against these polynomialcomplexity attacks. Another main challenge is to determine whether there exist some PBQC protocol resistant to channel imperfections, either losses or noise, between the verifiers and
Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary UAB by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary UAB whose implementation in NLQC requires extra quantum systems with dimensions exp(nΩ(1)), where n is the dimension of systems A and B. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in n.
In this paper we consider the family of diagonal ±1 valued unitaries Uε, indexed by an element of the Boolean hypercube ε∈{±1}n2, i.e. Uε∣i⟩A∣j⟩B=εij∣i⟩A∣j⟩B. We show that if Uε can be implemented in NLQC with constant accuracy for all ε, and the dependency on ε in the first round of the associated strategy is a polynomial of degree O(n41−δ), then the implementation of at least one Uε in NLQC requires resources scaling as exp(Ω((logn)2n2δ)). The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle.
For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier.
The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size 2poly(n) changes its output with probability above 2−Ω(n) when the answer of a random instance is flipped by changing a single leaf.
Abstract In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a position verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above.