1 Introduction↩︎

1.0.0.1 Position verification.

Is it possible to verify a quantum state’s location in space and time? In the field of quantum cryptography, this is ostensibly the goal of quantum position verification (QPV). A QPV protocol attempts to verify the physical location of a user (called the prover) by sending them challenges (which are, in general, quantum states) and receiving responses. Intuitively, the protocol is deemed secure if a successful prover, responding within some timing constraint, must be in a purported location \(L\). As argued by [1]–[3], secure position verification is impossible in the classical setting because a team of spoofers (all of whom are not in location \(L\)) can copy and forward messages to each other to simulate a fictitious prover in location \(L\). On the other hand, the No-Cloning Theorem of quantum mechanics stymies such copy-and-forwarding attacks, and in fact secure QPV protocols have been established in the bounded-qubits model [4]–[7] and the random oracle model [8].

One particularly intriguing motivation for QPV is concept of position-based cryptography, in which a user’s credential is established by their physical location (as opposed to being established by having some secret information such as a password or private key) [2]. Position-based cryptography includes tasks such as position-based encryption (i.e., an encrypted message can only be decrypted by recipients in an authorized physical location) or position-based signatures (i.e., a message’s signature ensures that it was authorized from a specific location). Recently, QPV has been generalized to privacy-preserving proofs of location that only reveal part of a prover’s location and nothing else [9] (i.e., a user can prove to the police that they were somewhere far from the scene of a crime, without revealing any other information about their specific whereabouts).

1.0.0.2 A conceptual gap.

However, closer examination reveals a gap between the intuitive goals of QPV and the formal notion of position verification considered thus far. In prior work, security of QPV was defined as follows: a team of spoofers \(\{\mathcal{P}_1,\ldots,\mathcal{P}_k\}\) can succeed in a QPV protocol with high probability only if at least one of the spoofers \(\mathcal{P}_i\) is in the correct location \(L\). This is a rather weak guarantee, however. Imagine trying to use QPV to prove that one is not near the scene of a crime. Unfortunately, the definition only guarantees that at least one spoofer wasn’t at the crime location; it doesn’t say anything about the other spoofers! In other words, the security definition of QPV does not rule out a spoofing strategy that is distributed across space and time.

We illustrate another conceptual difficulty with the security definition of QPV. Consider a natural generalization of position verification that we call trajectory verification: here we want to verify that a prover has traveled along a trajectory \(L(\cdot)\) described as a function of time \(t\). A natural approach is to run separate QPV protocols \(\left\{\Pi_i\right\}_i\) for many spacetime points \(\left\{(L(t_i),t_i)\right\}_i\), respectively, such that these points divide the trajectory into sufficiently small segments. An immediate problem is that the existing security guarantees of \(\Pi_1,\Pi_2,\ldots\) do not distinguish between whether a single prover has traveled along the trajectory \(L(\cdot)\) or whether an entire team \(\{\mathcal{P}_1,\mathcal{P}_2,\ldots\}\) of provers participated in the protocol, where each prover \(\mathcal{P}_i\) is stationed at location \(L(t_i)\), only participating in protocol \(\Pi_i\) at time \(t_i\). To rule out the latter scenario, one needs to explain why a line of provers is fundamentally different from a single prover that is moving!

1.0.0.3 This work.

These issues call for a notion of localizing the behavior of an adversary who might be a priori distributed in space and time. The main contributions of this paper are to define several notions of “quantum localization” and establish their feasibility via constructions in the (classical) ideal obfuscation model,¹ which can be heuristically instantiated using post-quantum indistinguishability obfuscation of classical circuits. We then show that these notions enable meaningful notions of trajectory verification, yielding the first feasibility result for verifying the trajectory of an entity through spacetime.

We believe that our notions of localization come closer to capturing the concept of secure position verification. They give operational meaning to tracking the physical location of quantum states and computations, and lay the proper foundation for more complicated tasks such as trajectory verification.

1.1 Entanglement Localization and Trajectory Verification↩︎

We present stronger security notions for QPV that we call quantum localization, or localization for short. Informally, these security notions will guarantee that any successful prover strategy (which may involve a team of provers \(\{\mathcal{P}_1,\ldots,\mathcal{P}_k\}\) moving around) must contain a specific object at the correct point \((L,t)\) in spacetime. By “contain,” we mean that there exists a procedure called the extractor acting only on the prover’s strategy at the point \((L,t)\) that recovers the desired object. In this paper we identify three types of objects that can be localized: entanglement, (unclonable families of) quantum states, and (copy-protectable) functionalities.

We first describe entanglement localization and then describe how to build on entanglement localization in order to achieve a meaningful notion of trajectory verification.

1.1.0.1 Entanglement Localization.

Let \(\psi\) be a bipartite entangled state on registers \(\mathbf{A}\) and \(\mathbf{B}\). Consider a QPV protocol where the verifiers generate \(\psi\), keep register \(\mathbf{A}\), and send register \(\mathbf{B}\) to the prover who is purportedly at spacetime point \((L,t)\). We say that the protocol localizes the entanglement in \(\psi\) at \((L,t)\) if for any (possibly nonlocal) prover strategy that is accepted with probability \(\eta\), there exists an extractor \(\mathcal{E}\) that acts on the quantum state at spacetime point \((L,t)\) and achieves the following. With probability \(\eta\), it outputs a register \(\mathbf{B}\) that, together with the verifier’s register \(\mathbf{A}\), is close to being in the state \(\psi\). In other words, it has recovered the entangled state \(\psi\) between register \(\mathbf{A}\) and the spacetime point \((L,t)\) with the same probability as the probability that the prover succeeds in the protocol. We formally define this in 8.

Entanglement localization captures the idea that, in order to be successful, a team of provers must ensure that the quantum entanglement in the state \(\psi\) arrives at spacetime point \((L,t)\). Suppose that \(\psi\) is a pure state that is maximally entangled across the \(V : P\) cut. By monogamy of entanglement, the verifier’s register \(\mathbf{A}\) must then be unentangled with any other location \(L' \neq L\) at time \(t\).

1.1.0.2 Trajectory Verification.

The notion of entanglement localization gives rise to a natural definition of trajectory verification. Let \(L(\cdot)\) denote a trajectory in spacetime. Intuitively, a trajectory verification protocol for \(L(\cdot)\) is secure if there exists a maximally entangled state \(\psi\) such that entanglement localization can be performed with respect to \(\psi\) at spacetime points \((L(t),t)\) for all time \(t\) along the trajectory \(L(\cdot)\). Importantly, the verifier’s part of \(\psi\) remains at the same register \(V\) throughout the protocol, while the prover’s part of \(\psi\) may travel around. This definition captures the idea of a single entity moving along the trajectory \(L(\cdot)\) by tracking the movement of the entanglement \(\psi\). If the prover is accepted by the protocol, monogamy of entanglement implies that \(\psi\) couldn’t have strayed from the trajectory \(L(\cdot)\).

We note that in order to repeatedly run an entanglement localization protocol on the same state, it must satisfy an additional completeness guarantee which we call non-destructive. That is, the prover’s state must remain intact after interacting with the verifier. Therefore, our focus in this work is on building non-destructive versions of quantum localization.

1.1.0.3 Construction.

We show how to construct secure trajectory verification in the ideal obfuscation model. In this model, the \({\sf Setup}\) samples the description of an efficient classical circuit, which all parties are given black-box access to throughout the protocol. Any protocol in this model can be heuristically instantiated in the plain model by applying a candidate post-quantum indistinguishability obfuscator to the classical circuit sampled by \({\sf Setup}\).

Trajectory verification as (informally) defined above immediately yields a protocol for entanglement localization as a special case (where the trajectory is stationary at \(L\)). For the sake of exposition we first describe (a simplified version of) the entanglement localization protocol, and then describe how to extend it to obtain trajectory verification. Moreover, we focus here on the “high success probability” regime, where we only guarantee extraction success if the prover passes the protocol with probability close to 1.

Assume that space is one-dimensional and the location to be verified is the origin \(L = 0\). Place verifiers \(\mathcal{V}_L,\mathcal{V}_R\) at locations \(-1\) and \(+1\), respectively. We assume messages travel one unit of space per unit time.

The entangled state used in our protocol is what we call a quantum anchor state. Let \(S \leq T \leq \mathbb{F}_2^{3n}\) be subspaces of dimension \(n\) and \(2n\), respectively, and let \(u, v \in \mathbb{F}_2^{3n}\) be some vectors. Let \({\sf CS}= \{x_1,x_2,\ldots\}\) denote some canonical set of \(2^n\) coset representatives of \(S\) within \(T\), indexed by \(i \in [2^n]\). We define the state \[\left|\Psi\right\rangle_{\text{\faAnchor}\text{\faShip}} = \frac{1}{\sqrt{2^n}} \sum_{i \in [2^n]} \left|i\right\rangle_{\text{\faAnchor}} \otimes \left|\psi_i\right\rangle_{\text{\faShip}}\] where for each \(i \in [2^n]\), \[\left|\psi_i\right\rangle_{\text{\faShip}} = \frac{1}{\sqrt{|S|}} \sum_{s \in S} (-1)^{\langle s, u \rangle} \left|s + x_i + v\right\rangle_{\text{\faShip}}~.\] We use the icons \(\text{\faAnchor}\) and \(\text{\faShip}\) to denote the “anchor” and “vessel” registers, respectively. The reason for this naming will become apparent shortly.

Readers familiar with unclonable cryptography may recognize \(\left|\psi_i\right\rangle\) as a coset state. That is, the state \(\left|\Psi\right\rangle\) can be seen as a uniform superposition over a set of \(2^n\) possible coset states, each defined with respect to subspace \(S\), dual shift \(u\), and primal shift \(v + x_i\) for some choice of \(x_i \in {\sf CS}\). Note further that \(\left|\Psi\right\rangle\) is maximally entangled across the \(\text{\faAnchor}: \text{\faShip}\) cut with Schmidt rank \(2^n\).

In the \({\sf Setup}\) phase of the protocol (run any time before time \(t = 0\)), the verifiers generate the quantum anchor state \(\left|\Psi\right\rangle\) corresponding to random subspaces \(S \leq T \leq \mathbb{F}_2^{3n}\) and shifts \(u,v \in \mathbb{F}_2^{3n}\). Furthermore, the verifiers prepare a classical oracle \(\mathcal{O}\) (i.e., ideal obfuscation of some classical functionality) which depends on \(S,T,u,v\) and whose behavior we describe shortly. The verifiers publish the oracle \(\mathcal{O}\), which all parties (honest or adversarial) can access as a black box. They also release the vessel register \(\text{\faShip}\) to the prover, while keeping hold of the entangled anchor register \(\text{\faAnchor}\).

In the “online” phase of the protocol (at time \(t = 0\)), the verifiers sample random strings \(a,b \in \{0,1\}^n\), the left verifier sends string \(a\), and the right verifier sends string \(b\). The honest prover with register \(\text{\faShip}\) at location \(L = 0\) gets \(a,b\) at time \(t = 1\). Then,

1. The honest prover coherently queries the oracle \(\mathcal{O}\) on input \(\left|a \oplus b, z\right\rangle\) where \(\left|z\right\rangle\) is the state of the vessel register \(\text{\faShip}\) in the standard basis. The oracle checks whether \(z \in T + v\) (For the honest prover, this will be true.) and if so, outputs a string \(r_0 = H(0,a \oplus b)\), where \(H\) is a random oracle.² Otherwise, the oracle outputs \(\bot\).

2. The honest prover then queries the oracle \(\mathcal{O}\) on input \(\left|a \oplus b,w\right\rangle\) where \(\left|w\right\rangle\) is the state of the vessel register \(\text{\faShip}\) in the Hadamard basis. The oracle checks whether \(w \in S^\perp + u\) (which will be the case) and if so, outputs a string \(r_1 = H(1,a \oplus b)\). Otherwise, the oracle outputs \(\bot\).

3. The honest prover returns \((r_0,r_1)\) back to the verifiers.

We note that after each query, the vessel register and the anchor state \(\left|\Psi\right\rangle\) have not been disturbed.

The verifiers check that the responses came back by time \(t = 2\), and that \(r_0,r_1\) are indeed equal to \(H(0,a\oplus b), H(1,a \oplus b)\).³ The idea is that the only way for the prover to have “unlocked” \(r_0,r_1\) is if it performed the honest strategy above in the correct location \(L = 0\).

As mentioned above, this is the basic idea behind a protocol that allows us to extract from any prover that passes with probability close to 1. We formalize this in 32. Then, in 9.1, we apply an appropriate notion of sequential repetition in order to establish a more general result, informally stated as follows.

We note that our extractor requires knowledge of \(S,T,u,v\), which it can obtain by making exponentially many queries to \({\mathcal{O}}\). Indeed, we do not require any computational (or query) bound on the extractor for the above notion to be meaningful, since monogamy-of-entanglement is an information-theoretic property. However, we do show that the extractor is efficient if given a secret “extraction key” \({\sf ek}= (S,T,u,v)\), which may be a useful feature, depending on the application.

Given our entanglement localization protocol, the extension to trajectory verification is simple. Let \(L(\cdot)\) be a physically realizable trajectory in spacetime that starts at time \(0\) and ends at \(\tau\), and the spatial points are all contained within the convex hull of the verifiers (i.e., strictly between \(L = -1\) and \(L = 1\)). Discretize time \(0 = t_1 < t_2 < \cdots < t_m = \tau\), and let \(L(t_i)\) denote the spatial location of the trajectory at time \(t_i\).

The trajectory verification protocol has the same \({\sf Setup}\) as the entanglement localization protocol. In the online phase of the protocol, the verifiers run \(m\) invocations of the entanglement localization protocol in sequence for spacetime points \((L(t_i),t_i)\), sending freshly sampled \(a_i,b_i\) each time. We can compose the entanglement localization guarantees of the QPV protocol above to obtain 37, informally stated as follows.

At this point, we hope the “anchor” and “vessel” terminology should appear natural. The \(\text{\faAnchor}\) part of the state \(\left|\Psi\right\rangle\) is “anchored” at the verifier’s location, while the \(\text{\faShip}\) part is launched into the spacetime region under the provers’ control. The provers can a priori perform arbitrarily complex operations on the vessel, but in the end, if they are to pass the trajectory verification protocol, they must faithfully sail the quantum vessel \(\text{\faShip}\) along the trajectory \(L(\cdot)\). The fact that the entanglement persists between the anchor and the points along the trajectory captures the fact that we are tracking the same quantum information through space and time.

1.2 State Localization↩︎

A curious aspect of the entanglement localization and trajectory verification protocols described above is that the verifier’s register (the quantum anchor) is never acted upon after the entangled state is prepared. In fact, the verifiers don’t even need this register to check the prover’s responses. Thus, a slightly different way to describe the generation of the anchor state is as follows.

• Sample \(S,T,u,v\) as above, and define an isometry \(\mathsf{Enc}_{S,T,u,v}\) that maps \[\mathsf{Enc}_{S,T,u,v}: \left|i\right\rangle \to \left|\psi_i\right\rangle = \frac{1}{\sqrt{|S|}} \sum_{s \in S} (-1)^{\langle s, u \rangle} \left|s + x_i + v\right\rangle.\]

• Prepare the maximally entangled state \[\frac{1}{\sqrt{2^n}}\sum_{i \in [2^n]}\left|i\right\rangle_\text{\faAnchor}\left|i\right\rangle_\text{\faShip}\] and apply \(\mathsf{Enc}_{S,T,u,v}\) to the \(\text{\faShip}\) register.

• Discard \(\text{\faAnchor}\).

Imagine, then, that instead of applying \(\mathsf{Enc}_{S,T,u,v}\) to half of a maximally entangled state, the verifiers sample a pure state \(\psi_k\) from some unclonable family of states \(\{\psi_k\}_{k \in [K]}\) (say, the BB84 states) and output \(\mathsf{Enc}_{S,T,u,v}\left|\psi_k\right\rangle\). If the purification of this sampling procedure is equivalent to the maximally mixed state, then this is completely identical from both the prover’s and extractor’s perspective, since neither touches the \(\text{\faAnchor}\) register. It follows then that at each intermediate time \(t_i\), the extractor acting on spacetime point \((L(t_i),t_i)\) will output a register in a state close to \(\mathsf{Enc}_{S,T,u,v}\left|\psi_k\right\rangle\). In fact, since the extractor knows \(S,T,u,v\), it can undo the isometry to recover \(\left|\psi_k\right\rangle\) itself.

Thus, even though there is no entanglement to keep track of anymore in this scenario, there is still a meaningful sense in which we have localized a quantum state \(\psi_k\) along the trajectory: At any given time \(t_i\), the state \(\psi_k\) cannot be found at any other location in space since otherwise the adversary / extractor would have been able to clone it.

This motivates the following general definition of state localization. Let \(\mathcal{S} = \{\psi_k \}_k\) denote a family of quantum states indexed by \(k\) (for example, BB84 states or coset states). Suppose the verifiers sample \(k\), generate (and potentially encode) \(\left|\psi_k\right\rangle\), and send the resulting state to the prover. We say that a protocol localizes the state family \(\mathcal{S}\) if for any (possibly nonlocal) prover strategy that is accepted with high probability, there exists an extractor \(\mathcal{E}\) that acts on the quantum state at spacetime point \((L,t)\) and outputs \(\left|\psi_k\right\rangle\) with high fidelity. Furthermore, the state extracted from \((L,t)\) must be unique, in that, in expectation over \(\psi_k \gets \mathcal{S}\), it is impossible for any adversary to output two copies of \(\psi_k\) at any time \(t\). We present a formal definition in 10.

By applying the techniques used to prove [thm:NDEL_overall,thm:TV_overall], we prove 39, informally stated as follows.

While state localization is closely related to entanglement localization, there are some meaningful differences. The extractor produces a quantum state (close to) \(\psi_k\) that is classically correlated with the verifiers’ choice of \(k\). That is, unlike in the case of entanglement localization, the verifier has an actual classical description \(k\) of the state being tracked, as opposed to some entangled register. Thus, there may exist some other side information in the protocol that also depends on \(k\), which may be a useful feature depending on the application. Furthermore, in the setting of purely classical verifiers (such as that of [10]) we cannot obtain entanglement localization, but state localization is still potentially possible (e.g., the verifiers can delegate the preparation of \(\psi_k\) to the prover).

1.2.0.1 Trajectory verification with localized states.

Similarly to how trajectory verification follows naturally from our (non-destructive) entanglement localization protocol, it is straightforward to see that one could build trajectory verification from our (non-destructive) state localization protocol as well. We do not make this explicit, and only present trajectory verification based on entanglement localization in the body.

1.3 Functionality Localization↩︎

Entanglement and state localization capture the idea that the prover must carry a specific quantum state to some spacetime point \((L,t)\). However, can we say anything about the prover’s computational capabilities at \((L,t)\)? This could be desirable in a scenario like export control of secret, proprietary programs (like a foundation language model), where a company or a government would like to guarantee that the ability to run the secret program is localized to a specific location (say within an authorized datacenter).

Let \(\mathcal{F} = \{ f_k \}_k\) denote a family of functions indexed by some key \(k\) (for example, a pseudorandom function family). Suppose that at the beginning of the protocol, the verifiers sample \(k\) privately. We say that a protocol localizes functionality \(\mathcal{F}\) if for any (possibly nonlocal) prover strategy that is accepted with high probability, there exists an extractor \(\mathcal{E}\) that acts on the quantum state at verified spacetime point \((L,t)\) and is able to compute \(f_k(x)\) for a random input \(x\). On the other hand, there must be no (efficient) adversary that can, for random inputs \(x,y\), compute \(f_k(x)\) and \(f_k(y)\) at two separate locations without communicating. In other words, the ability to compute \(f_k(x)\) has been localized to \((L,t)\), and no other location (at time \(t\)) has the ability to compute \(f_k\). This is formally defined in 13.

The notion of functionality localization is closely related to the notion of quantum copy-protection, which is the concept of encoding a function \(f\) in a quantum state \(\psi_f\) that can be used to evaluate \(f\), but cannot used to compute \(f\) in two locations that cannot communicate [11]. There are broad classes of function families that are known to be copy-protectable under various cryptographic assumptions and in various models (see e.g., [12]–[18]). Here, we show that any functionality \(\mathcal{F}\) that can in principle be copy-protected can also be localized. In fact, we don’t even need to know an explicit copy-protection scheme for \(\mathcal{F}\). Our construction relies on a combination of techniques described above as well as the “best-possible” copy-protection guarantees given by quantum state obfuscation [19], [20]. We defer further details to 2, and establish the following theorem, stated informally.

1.4 The Ideal Obfuscation Model↩︎

We now provide some more context on the ideal obfuscation model (also referred to as the classical oracle model) that we use to establish the security of our protocols. In this model, one can prepare and then “obfuscate” any polynomial-time computable classical functionality \(f\), and thereafter all entities are granted black-box (superposition) access to \(f\). That is, anyone can apply the unitary \(U_f : \left|x\right\rangle\left|z\right\rangle \to \left|x\right\rangle\left|z \oplus f(x)\right\rangle\) without learning anything else about \(f\).

The ideal obfuscation model has a long history of study in quantum cryptography. In particular, it has been used to establish the feasibility of primitives for which no prior construction existed, e.g. publicly-verifiable quantum money [21], signature tokens [22], copy-protection for unlearnable programs [12], witness encryption for QMA [23], and obfuscation for quantum circuits [20], [24]–[26].

While ideal obfuscation of classical circuits has long been known to be impossible to achieve for certain contrived classes of functionalities [27], the ideal obfuscation model remains a useful model in which to obtain feasibility results, for the following reasons.

• First, any construction in the ideal obfuscation model (that does not require obfuscating the contrived functions from [27]) yields a plausibly secure construction in the plain model by using indistinguishability obfuscation (iO) to obfuscate the function \(f\). While we may not have a formal reduction to the security of iO, it is a reasonable heuristic to expect that the plain model construction is secure. This is analogous to how the community proves security in the random oracle model and then replaces the random oracle with a concrete hash function in practice, without necessarily having a formal reduction to any security property of the hash function.

• Second, a recent work [28], building on [29], has shown that the (quantum-accessible) ideal obfuscation model can be instantiated from indistinguishability obfuscation plus the heuristic use of a hash function (as opposed to an obfuscator) modeled as a “pseudorandom oracle.” This brings the ideal obfuscation model even closer to the widely-used random oracle model in that the only cryptographic object we need to treat heuristically is a hash function, which can be instantiated with a cryptographic hash such as SHA3.

We also mention that our use of oracles is to be expected, as our protocols are strengthenings of plain position-verification, which (in the unbounded entanglement setting) is only known in the random oracle model [8]. It would be considered a major breakthrough to prove the security of any our protocols, or indeed position-verification itself, in the plain model.

Finally, we remark on a slight technical gap in the informal theorem statements above. While the ideal obfuscation model requires the circuit \(f\) to be obfuscated to be polynomial-time computable, many of our constructions are most simply described as using a random oracle (plus other manipulations) to define \(f\). Thus, in order to make \(f\) efficient, we technically have to replace the random oracle with a (post-quantum) pseudorandom function, which is known from any post-quantum one-way function [30]. Thus, all of our results additionally assume one-way functions.

1.5 Non-Localizability of \(f\)-BB84↩︎

Now that we have stronger notions of position verification and have shown how to achieve them, it is natural to wonder whether these notions can be achieved with simpler protocols. We show that the well-studied \(f\)-BB84 protocol does not satisfy entanglement localization. Let \(f(x,y)\) be a random boolean function. In this protocol, the honest prover at the proper location \(L\) receives classical challenges \(x,y\) as well as half of an EPR pair. It is supposed to compute a bit \(\theta = f(x,y)\) and measure its qubit in the standard or Hadamard basis according to \(\theta\) to obtain a bit \(b\), which it sends back in response. The verifier performs the same measurement on its half of the EPR pair and checks if it got the same outcome.

Unruh showed that if \(f\) is modeled as a random oracle, then unless the spoofers \(\{ \mathcal{P}_1,\ldots,\mathcal{P}_k\}\) make \(\exp(\Omega(n))\) queries to \(f\) (where we think of \(x,y\) as \(n\)-bit strings), then any successful spoofing strategy requires at least one of the provers \(\mathcal{P}_i\) to be in the correct location \(L\) [8]. Now, is it possible to strengthen Unruh’s result to show that the EPR entanglement can be localized to where the honest prover was supposed to be? We show that, perhaps surprisingly, this is not possible. We describe one attack here and will actually describe a slightly different one in 2.

Consider the following \(3\) prover strategy, pictured in 2. There are provers \(\mathcal{P}_L,\mathcal{P}_M,\mathcal{P}_R\) (for “left”, “middle”, and “right”). Prover \(\mathcal{P}_M\) is in the correct location but \(\mathcal{P}_L,\mathcal{P}_R\) are on either side of \(\mathcal{P}_M\). Suppose that \(\mathcal{P}_L\) and \(\mathcal{P}_R\) share a random quantum one-time pad key \(r,s \in \{0,1\}\) in superposition. Suppose that the leftmost verifier sends half of the EPR pair; call this qubit \(Q\). It gets intercepted by \(\mathcal{P}_L\), who applies a quantum one-time pad \(X^r Z^s\) to \(Q\), and forwards it to \(\mathcal{P}_M\). The middle prover \(\mathcal{P}_M\) gets the one-time padded qubit, along with \(x,y\). It computes \(\theta = f(x,y)\), and measures the qubit in the corresponding basis to obtain a bit \(c\). The middle prover \(\mathcal{P}_M\) then sends \(\theta,c\) to both \(\mathcal{P}_L\) and \(\mathcal{P}_R\). Both \(\mathcal{P}_L\) and \(\mathcal{P}_R\) compute \(b\) as follows: if \(\theta = 0\), then \(b = c \oplus r\), and otherwise \(b = c \oplus s\). All operations are controlled by the superposition of \(r,s\). It is easy to check that this strategy satisfies the timing constraints and will be accepted with probability \(1\).

Although the middle prover is performing the correct measurement, the quantum entanglement in the EPR pair cannot be localized to the middle prover. At all times in this strategy, the marginal state of the middle prover is completely uncorrelated with \(\theta\) and the verifier’s EPR qubit. Thus there is no way for the middle prover to locally extract the other end of the EPR pair; it has been nonlocally distributed between the three provers \(\mathcal{P}_L,\mathcal{P}_M,\mathcal{P}_R\).

Thus, (entanglement) localization is a rather strong security condition that doesn’t hold for all QPV protocols studied in the literature.

1.6 Outlook and Future Directions↩︎

1.6.0.1 Position-based cryptography.

In light of our new notions of localization and trajectory verification, it will be interesting to revisit implications for position-based cryptography. As mentioned, there has been a subtle but important gap between the goals of position-based cryptography and the previous formalizations of position security. In 10.2, we illustrate this gap by presenting an “attack” on the position-based signature protocol of [3] that does not violate their security definition but intuitively should not be allowed in any reasonable real-world application of position-based authentication. We then further discuss why we believe our concepts and techniques should provide a stronger foundation for position-based cryptography. We leave further exploration of new definitions and constructions of position-based cryptography to future work.

1.6.0.2 Future work.

Our work raises several other directions for future exploration, which we list here.

• In this work, we restrict our attention to one spatial dimension. While some subtleties typically arise when generalizing to more dimensions (see e.g. [8]), we expect that our techniques should apply in higher dimensions, and we leave a formalization of this to future work.

• A recent work [9] has shown how to build position commitments and zero-knowledge position-verification. Can we build on their techniques to obtain trajectory commitments and zero-knowledge localization protocols?

• [10], [31] have shown how to achieve position verification with purely classical communication. Can we obtain quantum localization and trajectory verification with only classical communication?

• Can we further generalize the notion of quantum localization? For example, can we localize any (unclonable) QMA witness, perhaps by integrating our techniques with recent work [28], [32] that shows how to non-destructively verify QMA witnesses?

• Our localization and trajectory verification protocols all rely on highly entangled and difficult-to-implement states. Might there exist simpler protocols that are more amenable to experimental realization in the short term? We remark that simpler localization protocols are likely easier to achieve if we drop the non-destructive requirement, but such protocols would not serve as building blocks to trajectory verification.

• Our protocols assume noiseless transmission of quantum states, and that the prover is in exactly the right position at the right time. Can we achieve more robust versions of localization and trajectory verification, which resist environmental noise and allow the prover some leeway in their declared position / trajectory?

• In this work, we discuss the way to achieve publicly verifiable trajectory verification and publicly verifiable localization schemes except publicly verifiable function localization (See 19 for more details). Can we construct a publicly verifiable function localization scheme?

1.6.0.3 Acknowledgments.

We thank Tal Malkin, Alex May, and Saachi Mutreja for helpful discussions. HY is supported by AFOSR award FA9550-23-1-0363, NSF awards CCF-2530159, CCF-2144219, and CCF-2329939, and by the Sloan Foundation. LO is supported by a NSF Graduate Fellowship.

2 Technical Overview↩︎

In this overview, we first introduce the main techniques used to construct trajectory verification. Along the way, we’ll see how to perform entanglement and state localization. Then, we’ll cover some additional ideas required to obtain functionality localization.

2.1 Entanglement Localization and Trajectory Verification↩︎

To develop our trajectory verification scheme, we first develop a non-destructive test of entanglement, next upgrade it to entanglement localization, and finally derive trajectory verification. A non-destructive test of entanglement distributes an entangled state between two parties, \(\mathcal{V}\) (the verifier) and \(\mathcal{P}\) (the prover), and then specifies an interactive protocol that can be repeatedly used to test whether the prover still holds the state entangled with the verifier. An entanglement localization scheme is a proof system where the prover can convince the verifier that the entanglement exists across the verifier’s state and a state within a specific defined region, such as an interval \([L-\Delta, L+\Delta]\). We first consider how to verify entanglement in a non-destructive manner.

2.1.0.1 Is verifying entanglement always destructive?

We begin with the standard approach for verifying one bit of entanglement. Suppose two parties \(\mathcal{V}\) (an honest verifier) and \(\mathcal{P}\) (a potentially adversarial prover) initially share an \({\sf EPR}\) pair. The prover \(\mathcal{P}\) may perform some operations on its subsystem, resulting in a joint state \(\rho_{\mathbf{A}\mathbf{B}}\), where \(\mathbf{A}\) is held by \(\mathcal{V}\) and \(\mathbf{B}\) is held by \(\mathcal{P}\). As discussed for example in [33], the entanglement can be tested via the following protocol:

1. \(\mathcal{V}\) samples a random bit \(b \overset{\$}{\gets}\left\{0,1\right\}\). If \(b=0\), it measures \(\mathbf{A}\) in the standard basis; otherwise, it measures \(\mathbf{A}\) in the Hadamard basis. Let the measurement outcome be \(x\). The verifier then sends \(b\) to \(\mathcal{P}\).

2. Upon receiving \(b\), the prover \(\mathcal{P}\) performs the corresponding measurement operation and outputs a value \(x'\).

If \(\mathcal{P}\) can perfectly predict the standard or Hadamard basis measurement outcome on \(\mathcal{V}\)’s side, i.e., \(x = x'\) with probability \(1\) over the choice of \(b\), then \(\mathcal{V}\) is convinced that its qubit was maximally entangled with \(\mathcal{P}\)’s system. However, this procedure necessarily collapses the entanglement, and at first glance this appears unavoidable.

Our main observation here is the following:

More concretely, we design two tests \(\Pi_{\sf ncol}\) and \(\Pi_{\sf col}\) for \(\mathcal{P}\). The test \(\Pi_{\sf ncol}\) is the non-collapsing test that we actually execute. We then argue, via an indistinguishability argument, that any prover passing \(\Pi_{\sf ncol}\) must also perform well in a corresponding collapsing test \(\Pi_{\sf col}\), which certifies the presence of entanglement.

2.1.0.2 Deploying decoy qubits.

We now present a first toy example. In addition to the original \({\sf EPR}\) pair shared between \(\mathcal{V}\) and \(\mathcal{P}\), we sample \(n\) random standard-basis qubits from \(\left\{\left|0\right\rangle,\left|1\right\rangle\right\}\) and \(n\) random Hadamard-basis qubits from \(\left\{\left|+\right\rangle,\left|-\right\rangle\right\}\). These \(2n\) qubits, together with the prover’s half of the \({\sf EPR}\) pair, are randomly shuffled into the register \(\mathbf{B}\), which now contains \(2n+1\) qubits.

To test for entanglement, instead of querying the unique (hidden) entangled qubit directly, \(\mathcal{V}\) proceeds as follows:

1. Sample a random basis (standard or Hadamard).

2. Send \(\mathcal{P}\) the indices of the \(n\) qubits prepared in that basis and request their measurement outcomes in the corresponding basis.

3. Check whether the answers are correct.

From the prover’s perspective, all \(2n+1\) qubits appear as random BB84 states and are thus maximally mixed. The \(2n\) additional qubits serve as decoys that hide the location of the entangled qubit. To succeed, \(\mathcal{P}\) must effectively retain all qubits, and hence preserve the entanglement. Discarding any qubit risks failing the test, since that qubit may be queried.

To formalize this intuition, consider the single-shot setting with a prover \(\mathcal{P}\) that passes the protocol with probability 1. Let \(S\) denote the indices of the standard-basis qubits, and consider some arbitrary position \(x \in S\). We claim that \(\mathcal{P}\) would also answer correctly if, instead of querying \(S\), we queried \((S \setminus \left\{x\right\}) \cup \left\{e\right\}\), where \(e\) is the index of the entangled qubit. Here, correctness for \(e\) means consistency with the standard-basis measurement outcome on \(\mathbf{A}\). This follows because \(S\) and \((S \setminus \left\{x\right\}) \cup \left\{e\right\}\) are indistinguishable from the prover’s perspective.

This illustrates our earlier principle: the test on \(S\) is non-collapsing, while the test on \((S \setminus \left\{x\right\}) \cup \left\{e\right\}\) is collapsing, as it measures the entangled qubit.

However, this approach has a clear limitation. If the test is repeated multiple times, \(\mathcal{P}\) may learn which qubit is never queried, thereby identifying the entangled qubit. Once identified, the prover can discard it and still answer future queries correctly.

2.1.0.3 Reusable security via coset states.

To address this issue, we introduce a stronger method for hiding the decoys, based on coset states. A coset state \(\left|A_{s,s'}\right\rangle\), for a subspace \(A \leq \mathbb{F}_2^n\) of dimension \(n/2\) and \(s, s' \in \mathbb{F}_2^n\), is defined as \[\left|A_{s,s'}\right\rangle = \frac{1}{\sqrt{|A|}} \sum_{a \in A} (-1)^{\left \langle {a,s'} \right \rangle} \left|a+s\right\rangle.\] This state admits the following alternative interpretation:

1. Prepare an \(n\)-qubit state in which the first \(n/2\) qubits are random Hadamard-basis states, and the remaining \(n/2\) qubits are random standard-basis states.

2. Sample a random change-of-basis (invertible) matrix \(U_{\sf shift} \in \mathbb{F}_2^{n \times n}\) and apply the unitary \(\mathcal{U}_{\sf shift}\) defined as \[\mathcal{U}_{\sf shift}\left|x\right\rangle := \left|U_{\sf shift} x\right\rangle.\]

The second step plays a crucial role: without knowledge of \(U_{\sf shift}\), the subspace \(A\) and the cosets \(A+s\) and \(A^\perp + s'\) are computationally hidden. In particular, given \(\left|A_{s,s'}\right\rangle\), one cannot distinguish between:

• Access to membership oracles \(\mathcal{O}_{A+s}\) and \(\mathcal{O}_{A^\perp+s'}\), and

• Access to membership oracles \(\mathcal{O}_{B+s}\) and \(\mathcal{O}_{C+s'}\), where \(B\) and \(C\) are random super-subspaces of dimensions \(n - \omega(\log n)\) containing \(A\) and \(A^\perp\), respectively.

Here, \(\mathcal{O}_S\) denotes the membership oracle for a set \(S\), outputting \(\top\) on inputs in \(S\) and \(\bot\) otherwise.

Intuitively, the random change of basis hides the “positions” of the standard- and Hadamard-basis qubits, in a strictly stronger manner than the random permutation from before. We now apply this idea to also hide the positions of entangled qubits. Consider the following construction:

1. Let \(\text{\faAnchor}\) be an \(n\)-qubit register and \(\text{\faShip}\) a \(3n\)-qubit register. Initialize the first \(n\) qubits of \(\text{\faShip}\) as random Hadamard-basis states, the next \(n\) qubits as halves of \({\sf EPR}\) pairs with \(\text{\faAnchor}\), and the final \(n\) qubits as random standard-basis states.

2. Sample a random change-of-basis matrix \(U_{\sf shift} \in \mathbb{F}_2^{3n \times 3n}\) and apply the unitary \(\mathcal{U}_{\sf shift}\) defined as \[\mathcal{U}_{\sf shift}\left|x\right\rangle := \left|U_{\sf shift} x\right\rangle\] to the register \(\text{\faShip}\).

We refer to the resulting state as the anchor state \(\left|\Psi^{\sf sk}\right\rangle_{\text{\faAnchor}\text{\faShip}}\), where \({\sf sk}= (S,T,u,v)\).

1. \(S\) is the subspace spanned by the first \(n\) columns of \(U_{\sf shift}\).

2. \(T\) is the subspace spanned by the first \(2n\) columns of \(U_{\sf shift}\).

3. \(u := U_{\sf shift}^{-t} u'\) where \(u'\) is the vector obtained by appending \(2n\) zeros to the vector of Hadamard-basis values (where \(\left|+\right\rangle\) is mapped to \(0\) and \(\left|-\right\rangle\) is mapped to \(1\)), and \(U_{\sf shift}^{-t}\) is the inverse transpose of \(U_{\sf shift}\).

4. \(v := U_{\sf shift} v'\) where \(v'\) is the vector obtained by appending \(2n\) zeros before the vector of the standard-basis values.

We clarify some facts here. First, if we measure \(\text{\faShip}\) in the standard basis, we will get a vector in \(T + v\). If we measure \(\text{\faShip}\) in the Hadamard basis, we will get a vector in \(S^\perp + u\). Combining our previous non-destructive test with the hiding property achieved by oracles, we define the following test:

1. In the setup phase, \(\text{\faAnchor}\) is given to \(\mathcal{A}\) and \(\text{\faShip}\) is given to \(\mathcal{B}\). Sample \(\theta \overset{\$}{\gets}\{0,1\}\) and \(s \overset{\$}{\gets}\{0,1\}^{\sf{\lambda}}\). \(\theta\) is given to \(\mathcal{B}\).

2. If \(\theta=0\), give the oracle \(\mathcal{O}_{T+v}^{\sf ncol}\) to \(\mathcal{B}\), where the oracle is defined as follows:

   • \(\mathcal{O}_{T+v}^{\sf ncol}\): On input \(z\), check whether \(z \in T + v\). Output \(s\) if it is, and output \(\bot\) otherwise.

   If \(\theta=1\), give the oracle \(\mathcal{O}_{S^\perp+u}^{\sf ncol}\) to \(\mathcal{B}\), where the oracle is defined as follows:

   • \(\mathcal{O}_{S^\perp+u}^{\sf ncol}\): On input \(z\), check whether \(z \in S^\perp + u\). Output \(s\) if it is, and output \(\bot\) otherwise.

   \(\mathcal{B}\) is supposed to return \(s\).

An honest \(\mathcal{B}\) can simply perform the corresponding basis evaluation coherently. That is, for \(\theta=0\), it computes \(\mathcal{O}_{T+v}^{\sf ncol}\) coherently on register \(\text{\faShip}\) and outputs the measurement result. For example, 3 shows the non-collapsing test when \(U_{\sf shift}=I\) and \(\theta=0\). Only the correctness of the standard-basis qubits is tested. One may notice that this is a non-collapsing test, and the state is unchanged after the test is completed.

Now, using the subspace bloating lemma, we design a collapsing test that is indistinguishable from the non-collapsing test from \(\mathcal{B}\)’s perspective.

1. In the setup phase, \(\text{\faAnchor}\) is given to \(\mathcal{A}\) and \(\text{\faShip}\) is given to \(\mathcal{B}\). Sample \(\theta \overset{\$}{\gets}\{0,1\}\) and a random oracle \(\mathcal{O}_{\sf random}\). \(\theta\) is given to \(\mathcal{B}\).

2. If \(\theta=0\), give the oracle \(\mathcal{O}_{T+v}^{\sf col}\) to \(\mathcal{B}\), where the oracle is defined as follows:

   • \(\mathcal{O}_{T+v}^{\sf col}\): On input \(z\), check whether \(z \in T + v\). Output \(\mathcal{O}_{\sf random}({\sf Can}_S(z))\) where \({\sf Can}_S(z)\) is the canonical representation of coset \(S+z\) if it is, and output \(\bot\) otherwise.

   If \(\theta=1\), give the oracle \(\mathcal{O}_{S^\perp+u}^{\sf col}\) to \(\mathcal{B}\), where the oracle is defined as follows:

   • \(\mathcal{O}_{S^\perp+u}^{\sf col}\): On input \(z\), check whether \(z \in S^\perp + u\). Output \(\mathcal{O}_{\sf random}({\sf Can}_{T^\perp}(z))\) where \({\sf Can}_{T^\perp}(z)\) is the canonical representation of coset \(T^\perp + z\) if it is, and output \(\bot\) otherwise.

3. If \(\theta = 0\), the verifier measures \(\text{\faAnchor}\) in the standard basis to obtain \(x\). Otherwise, if \(\theta = 1\), the verifier measures \(\text{\faAnchor}\) in the Hadamard basis to obtain \(x\).

One can think of the canonical representation of a coset as a unique identifier for the coset. Now suppose that \(\theta=0\) and the prover coherently computes \(\mathcal{O}_{T+v}^{\sf col}\) on register \(\text{\faShip}\). A measurement on the oracle output will collapse the state according to which coset of \(S\) the vector \(z\) belongs to, where \(z\) is the standard-basis value on \(\text{\faShip}\). This is equivalent to measuring all entangled qubits in the standard basis. For example, 4 shows the collapsing test when \(U_{\sf shift}=I\) and \(\theta=0\).

In the collapsing test, each potential measurement result \(x\) obtained by the verifier corresponds to a different input on which the honest prover queried \(\mathcal{O}_{\sf random}\). In the main proof, we show that any (potentially adversarial) prover that passes with probability close to \(1\) in the non-collapsing test will yield the following behavior in the collapsing test with overwhelming probability:

• If \(\theta=0\), the only input on which \(\mathcal{O}_{\sf random}\) is accessed is \({\sf Can}_S(U_{\sf shift}(0^n \times x \times 0^n) + v)\), where \(x\) is the standard-basis measurement result obtained by the verifier.

• If \(\theta=1\), the only input on which \(\mathcal{O}_{\sf random}\) is accessed is \({\sf Can}_{T^\perp}(U_{\sf shift}^{-t}(0^n \times x \times 0^n) + u)\), where \(x\) is the Hadamard-basis measurement result obtained by the verifier.

Hence, we can test entanglement by repeatedly asking the prover to answer non-collapsing tests. If the prover is able to answer all of them, they would also succeed in the collapsing test, and we will be convinced that the prover is holding the entanglement. Indeed, a prover that passes the collapsing test will predict the verifier’s standard / Hadamard basis measurement results, allowing the extraction of EPR pairs following the strategy of [33] .

2.1.0.4 Non-localizability of \(f\)-BB84.

We now move to the second component mentioned above: Localization of entanglement. As discussed in the introduction, the famous \(f\)-BB84 protocol does not satisfy entanglement localization. Here we give an alternative attack on this protocol that better conveys the motivation for our own construction.

Consider the following strategy involving three provers. There are provers \(\mathcal{P}_L\), \(\mathcal{P}_M\), and \(\mathcal{P}_R\) (for “left",”middle", and “right"). Prover \(\mathcal{P}_M\) is in the correct location, while \(\mathcal{P}_L\) and \(\mathcal{P}_R\) are positioned on either side of \(\mathcal{P}_M\). Upon receiving the \({\sf EPR}\) pair \(\left|\Phi\right\rangle_{\mathbf{A}\mathbf{B}}\), the prover applies the following unitary: \[\left|x\right\rangle_{\mathbf{B}} \rightarrow \frac{1}{\sqrt{2}} \sum_{b \in \left\{0,1\right\}} \left|b\right\rangle_{\mathbf{L}} \left|b\right\rangle_{\mathbf{M}_0} \left|b \oplus x\right\rangle_{\mathbf{M}_1} \left|b \oplus x\right\rangle_{\mathbf{R}}\] and sends \(\mathbf{L}\), \(\mathbf{M}= \mathbf{M}_0 \otimes \mathbf{M}_1\), and \(\mathbf{R}\) to \(\mathcal{P}_L\), \(\mathcal{P}_M\), and \(\mathcal{P}_R\), respectively. It can be seen that there is no entanglement between \(\mathbf{A}\) and \(\mathbf{M}\). To pass the challenge, the prover does the following.
If \(\theta = 0\):

• The middle prover \(\mathcal{P}_M\) sends \(\mathbf{M}_1\) to \(\mathcal{P}_L\) and \(\mathbf{M}_0\) to \(\mathcal{P}_R\).

• The left prover \(\mathcal{P}_L\) measures \(\mathbf{L}\) and \(\mathbf{M}_1\). If the bits are the same, it outputs \(0\); otherwise, it outputs \(1\).

• The right prover \(\mathcal{P}_R\) measures \(\mathbf{R}\) and \(\mathbf{M}_0\). If the bits are the same, it outputs \(0\); otherwise, it outputs \(1\).

If \(\theta = 1\):

• The middle prover \(\mathcal{P}_M\) sends \(\mathbf{M}_0\) to \(\mathcal{P}_L\) and \(\mathbf{M}_1\) to \(\mathcal{P}_R\).

• The left prover \(\mathcal{P}_L\) outputs \(0\) if its state is \(\frac{1}{\sqrt{2}} \left|00\right\rangle_{\mathbf{L}\mathbf{M}_0} + \frac{1}{\sqrt{2}} \left|11\right\rangle_{\mathbf{L}\mathbf{M}_0}\); otherwise, it outputs \(1\).

• The right prover \(\mathcal{P}_R\) outputs \(0\) if its state is \(\frac{1}{\sqrt{2}} \left|00\right\rangle_{\mathbf{R}\mathbf{M}_1} + \frac{1}{\sqrt{2}} \left|11\right\rangle_{\mathbf{R}\mathbf{M}_1}\); otherwise, it outputs \(1\).

Intuitively, this attack works because the left prover and the right prover “encrypt” the answer, such that the answer is stored in the interference between \(\mathbf{M}\) and \(\mathbf{L}\mathbf{R}\), while the middle prover has no clue about the answer when receiving the challenge. The middle prover does not measure anything, and the measurement is delayed until the global interference becomes local at the left and right provers.

2.1.0.5 Forcing a measurement via monogamy-of-entanglement.

To bypass this attack, the key idea is to force the prover to perform a particular “measurement” (in quotes because in reality they will be performing a non-destructive oracle query) at the position of the middle prover. More precisely, we want to ensure that the prover demonstrates its ability, in principle, to measure the state in a specific basis. We begin by replacing the random basis test on the \({\sf EPR}\) pair with a non-destructive test for entanglement:

1. In the setup phase, \(\text{\faAnchor}\) is given to \(\mathcal{A}\) and \(\text{\faShip}\) is given to \(\mathcal{B}\). Sample \(s \overset{\$}{\gets}\{0,1\}^{\sf{\lambda}}\).

2. The left verifier \(\mathcal{V}_L\) samples \(x_L\), and the right verifier \(\mathcal{V}_R\) samples \(x_R\). Both \(x_L\) and \(x_R\) are broadcast at the appropriate time to ensure they meet at the correct position.

3. The middle prover computes \(\theta = f(x_L, x_R)\) and performs the following:

   • If \(\theta = 0\), it is granted access to the oracle \(\mathcal{O}_{T+v}^{\sf ncol}\) and performs the coherent standard-basis measurement described above.

   • If \(\theta = 1\), it is granted access to the oracle \(\mathcal{O}_{S^\perp + u}^{\sf ncol}\) and performs the coherent Hadamard-basis measurement described above.

   • It broadcasts the result.

4. Both the left and right verifiers receive the result broadcast by the prover. The verifier returns \(\top\) if both messages are on time and correct (equal to \(s\)); otherwise, it returns \(\bot\).

One may ask how the prover can be given access to an oracle during the middle of the computation. It can be assumed that there is a class of oracles indexed by \(x_L, x_R\), and a particular oracle is selected for the parties once they know both \(x_L\) and \(x_R\).

Now, actually proving the extractability of this simple protocol appears challenging. Our solution is to repeat this protocol twice: one standard round followed by one Hadamard round, or vice versa. For example, let’s consider the case where the first round is a standard-basis round and the second round is a Hadamard-basis round.

1. In the setup phase, \(\text{\faAnchor}\) is given to \(\mathcal{A}\) and \(\text{\faShip}\) is given to \(\mathcal{B}\). Sample \(s_0, s_1 \overset{\$}{\gets}\{0,1\}^{\sf{\lambda}}\).

2. The first round has \(\theta_0 = 0\). The prover is granted access to the oracle \(\mathcal{O}_{T+v}^{\sf ncol}\) with \(s_0\) encoded as the secret and performs the coherent standard-basis measurement described above.

3. After a brief interval, the second round arrives with \(\theta_1 = 1\). The prover is granted access to the oracle \(\mathcal{O}_{S^\perp + u}^{\sf ncol}\) with \(s_1\) encoded as the secret and performs the coherent Hadamard-basis measurement described above.

4. Both the left and right verifiers receive the results broadcast by the prover. The verifier returns \(\top\) if all messages are on time and correct; otherwise, it returns \(\bot\).

Now, let’s examine how this two-round protocol prevents the attack described above. Suppose there are three provers \(\mathcal{P}_L, \mathcal{P}_M, \mathcal{P}_R\) that succeed at passing the protocol, but where only \(\mathcal{P}_M\) is at the correct spacetime location. Furthermore, suppose that \(\mathcal{P}_M\) fails to “measure” and determine the answer for the first challenge at the correct location and time. In this case, the strategy can be recast as a successful adversary \(\mathcal{A} = (\mathcal{A}_L, \mathcal{A}_M, \mathcal{A}_R)\) in the following monogamy-of-entanglement type game.⁶

1. The challenger generates \(\left|\Psi^{{\sf sk}}\right\rangle\) and gives the register \(\text{\faShip}\) to \(\mathcal{A}_M\).

2. \(\mathcal{A}_M\) generates a bipartite state on \(\mathbf{L}\mathbf{R}\). It sends \(\mathbf{L}\) to \(\mathcal{A}_L\) and sends \(\mathbf{R}\) to \(\mathcal{A}_R\).

3. The challenger samples \(s_0, s_1 \overset{\$}{\gets}\{0,1\}^{\sf{\lambda}}\). It gives \(\mathcal{O}_{T+v}^{\sf ncol}\) to \(\mathcal{A}_L\) that encodes \(s_0\) as its underlying secret, and it gives \(\mathcal{O}_{S^\perp + u}^{\sf ncol}\) to \(\mathcal{A}_R\) that encodes \(s_1\) as the underlying secret. In addition, it gives \(s_0\) to \(\mathcal{A}_R\).

4. \(\mathcal{A}_L\) returns \(s_0'\) and \(\mathcal{A}_R\) returns \(s_1'\).

5. The challenge is passed if \(s_0' = s_0\) and \(s_1' = s_1\).

Intuitively, the reduction works as follows: \(\mathcal{P}_M\) corresponds to \(\mathcal{A}_M\), the left prover \(\mathcal{P}_L\)’s process for solving the \(\mathcal{O}_{T+v}^{\sf ncol}\) challenge is used to construct \(\mathcal{A}_L\), and the right prover \(\mathcal{P}_R\)’s process for solving the \(\mathcal{O}_{S^\perp + u}^{\sf ncol}\) challenge is used to construct \(\mathcal{A}_R\). Due to the structure of the game, we also have to include the correct “left” answer \(s_0\) in the view of the right prover, which is a non-standard variant of monogamy-of-entanglement.

In 6, we show, via a sequence of reductions, that this game is hard for any adversary to win with probability better than \(\frac{1}{2} + {\sf negl}({\sf{\lambda}})\). Thus, we can eliminate this type of prover, meaning that any successful prover must indeed “measure” (meaning query the oracle on its state) at the correct location and time. Finally, we argue that this implies the existence of an extractor that, using quantum recording techniques [34], can obtain either the result of measuring \(\text{\faShip}\) in the standard or the Hadamard basis at the correct location and time. By the previous entanglement verification arguments, we can thus localize the entanglement to the desired spacetime location.

2.1.0.6 Trajectory verification.

As mentioned earlier, trajectory verification follows fairly naturally from our entanglement localization protocol. At a high level, the verifier first sends the vessel register \(\text{\faShip}\) to the prover, and then runs the entanglement localization protocol at a series of steps along the prover’s claimed trajectory. In slightly more detail, at each step, the verifier sends a random standard- or Hadamard- basis challenge.⁷ Therefore, each pair of steps gives rise to a slightly modified version of the two-round protocol described above, where the cadence is not fixed standard followed by Hadamard, but rather both are randomly chosen. We show that in this modified game, one can still extract entanglement from any successful prover at the time of the first challenge. This means that one can extract entanglement from the prover at any step on their trajectory, assuming they have a high probability of passing all challenges. This is formalized in 9.2.

2.1.0.7 Optimizations and applications.

We conclude by highlighting two additional features of our constructions. First, while the informal guarantees stated above only yield meaningful extraction when the adversary succeeds with probability \(1-o(1)\), this limitation can be overcome via sequential repetition. By executing sufficiently many copies of the localization protocol in rapid succession, we can amplify soundness so that any prover accepted with non-negligible probability must still contain the localized object at the verified spacetime point. In this way, our localization guarantees can be strengthened to hold against adversaries whose success probability is merely inverse polynomial.

Second, we discuss how to upgrade our protocols to achieve public verifiability. Intuitively, because the verification procedure is implemented using public classical oracles, one can arrange the protocol so that anyone with oracle access can verify the prover’s responses, without requiring access to any secret verification key. We defer the precise formulation and construction of publicly-verifiable localization protocols to 10.1. After that, in 10.2, we discuss broader implications for position-based cryptography and related applications.

2.2 Functionality Localization↩︎

Functionality localization can be seen as a strengthening of quantum copy-protection, which enables encoding a function \(f\) (sampled from some family \(\mathcal{F}\)) into a quantum state \(\rho_f\) such that (i) \(\rho_f\) can be used to compute \(f(x)\) for any input \(x\), and (ii) no adversary can create two disjoint registers that can simultaneously be used to compute \(f\) (over some distribution \(\mathcal{D}\) on inputs \(x\)).

That is, copy-protection establishes that certain functionalities can be rendered unclonable, meaning they cannot exist in two places at once. This then raises the possibility that functionalities can be localized! In this work, we show that any functionality \(\mathcal{F}\) that can in principle be copy-protected, can also be localized, in the classical ideal obfuscation model.⁸

Our construction combines “best-possible” copy-protection with the techniques introduced above. A best-possible copy-protector is a scheme that takes as input a function \(f \gets \mathcal{F}\) and outputs a state \(\rho_f\) such that, if there exists any method of copy-protecting \(f\), then \(\rho_f\) is itself a copy-protected version of \(f\). The idea of best-possible copy-protection was introduced by [19], who showed that any “quantum state obfuscator” serves as a best-possible copy protection scheme. Quantum state obfuscation was then shown to exist in the classical oracle model [20].

Let \({\sf QSO}\) be a quantum state obfuscator, let \(({\sf Auth},\mathsf{Ver})\) be a message authentication code, and consider the following (simplified) proposal for functionality localization.

• In the setup phase, the verifiers samples a functionality \(f \gets \mathcal{F}\), an authentication key \({\sf sk}\), and a random coset state \(\left|S_{v,u}\right\rangle\). Let \(\widehat{f}_{\sf sk}\) be the functionality that, on input \(x\), outputs \(f(x)\) along with a signature \(\sigma\) on the pair \((x,f(x))\). Output \(\rho_f \gets {\sf QSO}(\widehat{f}_{\sf sk})\) and \(\left|S_{v,u}\right\rangle\).

• In the online phase, the verifiers sample \(\theta \gets \{0,1\}, x \gets \mathcal{D}\), and a random oracle \(\mathcal{O}_{\sf random}\), and do the following.

  • If \(\theta = 0\), they send \(\theta,x\) to the prover along with an oracle \(\mathcal{O}_{{\sf sk},S,v}\) that takes as input \((z,x,y,\sigma)\) and if (i) \(z \in S+v\) and (ii) \(\mathsf{Ver}({\sf sk},(x,y),\sigma) = \top\), outputs \({\mathcal{O}}_{\sf random}(x,y)\).

  • If \(\theta = 1\), they send \(\theta,x\) to the prover along with an oracle \(\mathcal{O}_{{\sf sk},S^\perp,u}\) that takes as input \((z,x,y,\sigma)\) and if (i) \(z \in S^\perp+u\) and (ii) \(\mathsf{Ver}({\sf sk},(x,y),\sigma) = \top\), outputs \({\mathcal{O}}_{\sf random}(x,y)\).

• The honest prover, sitting at the correct spacetime point, uses \(\rho_f\) to compute \(f(x), \sigma_{x,f(x)}\), and then queries its oracle using either \(\left|S_{u,v}\right\rangle\) in the standard or Hadamard basis to obtain the value \(\mathcal{O}_{\sf random}(x,f(x))\), which it sends back to the verifier.

We note that there are several ways in which our final protocol differs from this simplified description, and we refer the reader to 9.4 for more details.

The intuition here is that, in order to succeed in the protocol, the prover must query their oracle at the correct location on \(z,x,f(x),\sigma_{x,f(x)}\), where \(z\) is either in \(S+v\) or \(S^\perp + u\). On the other hand, due to the security of the message authentication code and the hiding of \({\sf QSO}\), they will not be able to learn a signature \(\sigma_{x,y}\) on any \(y \neq f(x)\). Hence, the oracle \(\mathcal{O}_{\sf random}\) will be queried on \((x,f(x))\) but not on \((x,y)\) for any \(y \neq f(x)\). This yields the existence of an extractor that, using quantum recording techniques, can extract the value of \(f(x)\) from any successful adversarial prover at the location to be verified. We note that we crucially rely on the techniques developed above in the context of entanglement localization in order to establish that the adversary must indeed query their oracle at the correct spacetime location. In particular, even though there is no entanglement in this setting, we can view a random coset state as a “degenerate” version of the anchor state described above with the number of EPR pairs set to 0, and our techniques carry over naturally to this setting.

3 Preliminaries↩︎

3.1 General Notation↩︎

In many contexts, objects are parameterized by a security parameter \({\sf{\lambda}}\in\mathbb{N}\), which is often omitted to reduce clutter. We write PPT and QPT to denote probabilistic polynomial-time and quantum polynomial-time, respectively. Algorithms are denoted with calligraphic letters, such as \(\mathcal{A},{\mathcal{B}},\mathcal{P},\mathcal{V}\). Quantum registers are denoted with bold letters, such as \(\mathbf{A},\mathbf{B},\mathbf{X}\). We write \({\sf negl}(\lambda)\) to denote a negligible function in \(\lambda\). For a protocol \(\sf Prot\) and two parties \(\mathcal{P}\) and \(\mathcal{V}\) (prover and verifier), we write \(Y_{\mathcal{P}},Y_{\mathcal{V}}\gets{\sf Prot}(\mathcal{P}(\mathbf{A})\rightleftharpoons \mathcal{V}(\mathbf{B}))(x)\) to denote the experiment where \(\mathcal{P}\) and \(\mathcal{V}\) interact by running \(\sf Prot\) with public input \(x\), private prover input \(\mathbf{A}\), and private verifier input \(\mathbf{B}\). Here, \(Y_{\mathcal{P}}\) is some set of prover outputs and \(Y_{\mathcal{V}}\) is some set of verifier outputs. \(Y_{\mathcal{V}}\) typically includes a bit \(b\in\{\top,\bot\}\) known as the acceptance decision, with \(\top\) meaning the verifiers accept and \(\bot\) meaning that they reject.

3.2 Modeling Computations and Interactions in Spacetime↩︎

In this section, we describe our model for how algorithms and interactive protocols take place in physical spacetime, which will be important for the interpretation of our main results. This model is somewhat new to our work, but is inspired by similar sections in [35],[8], and [9]. Note that later sections of this paper, as well as our main results, do not rely closely on the wording of this section — instead, they tend to use terminology of a broader and more standard flavor. We strongly believe that our results are general enough that there is a wide variety of acceptable modeling choices under which they can retain correctness and meaningful interpretability.

3.2.0.1 Spacetime.

All of our protocols are set in a bounded one-dimensional space⁹, represented as \([-1,1]\). This is the line segment between two statically placed verifiers, \(\mathcal{V}_L\) at position \(-1\) and \(\mathcal{V}_R\) at position \(1\). We model time as \(\mathbb{R}^{\geq0}\), and we assume that all parties have access to a synchronized clock that reports the current time \(t \in \mathbb{R}^{\geq0}\). Units of space and time are taken such that light travels 1 unit of space in 1 unit of time. A point in spacetime is a pair \((L,t) \in [-1,1]\times\mathbb{R}^{\geq0}\), combining a spatial point with a time.

3.2.0.2 Messages.

We always consider messages to be directional — i.e. they travel either only to the left, or only to the right — and to travel with speed exactly 1 (the speed of light). We treat this process as the movement of a physical quantum register through space at the speed of light. In general, a message is a quantum state, although we often distinguish between the classical and quantum parts of a given message (for example, a party may send a string \(x\) and a qubit \(\left|\psi\right\rangle\) in the same message).

3.2.0.3 Algorithms.

We define the following model of computation in spacetime. An algorithm consists of a finite number of movable “cells”, which are quantum registers labeled \(\mathbf{R}_1,\mathbf{R}_2,\dots,\mathbf{R}_M\). Corresponding to each cell is a predetermined, continuous trajectory through space, which we’ll label \(T_1,\dots,T_M:\mathbb{R}^{\geq0}\to[-1,1]\). \(T_i(t)\) denotes the spatial location of cell \(\mathbf{R}_i\) at time \(t\). Cells can move at any speed up to the speed of light. Inputs are given to an algorithm by setting the initial value of some cells designated as input cells. Additionally, for each message that could possibly be sent or received by the algorithm, we add a cell which travels along the same path as this message, in perpetuity or until the message goes “out of bounds”, in which case the cell lingers at \(-1\) or \(1\). Prior to the departure time of a message, its corresponding cell will simply be dormant in the message’s starting location. The reason for this addition will become clear in the next paragraph.

The computational units of an algorithm are contained at the intersection points between its cells¹⁰ — let \(X\) be the set containing all of these points. At each intersection point \((L,t)\in X\), the algorithm contains a quantum circuit \(C_{L,t}\) acting on all of the cells which intersect there. \(C_{L,t}\) can implement any unitary on these cells, and the output registers can be arbitrarily subdivided among the participating cells. The size of a circuit, denoted \(|C_{L,t}|\), refers to the number of gates used to implement it, taken from some fixed universal quantum gate set. No matter the size of a circuit, it is always assumed to be an instantaneous operation. An algorithm is said to eventually terminate if \(X\) is finite, and it is said to have terminated whenever the last intersection point is reached. At termination, some of its cells are designated as outputs, and the rest discarded. As mentioned above, all messages are also treated as cells — to send a message, the algorithm transfers some information into the cell having that message’s trajectory, which occurs at the intersection point corresponding to the message departing. To receive a message, an algorithm might place a SWAP circuit between a message cell and another ancilla cell, for example.

We sometimes specify that a family of algorithms \(\{\mathcal{A}_{\sf{\lambda}}\}_{\sf{\lambda}}\) is QPT, which is defined with respect to a security parameter, and abbreviated as “\(\mathcal{A}\) is QPT” if dependence on \({\sf{\lambda}}\) is clear from context. Let \(X_{\sf{\lambda}}\) and \(\{C_{{\sf{\lambda}}}^{L,t}\}_{(L,t)\in X_{\sf{\lambda}}}\) be the sets of intersection points and circuits, respectively, for \(\mathcal{A}_{\sf{\lambda}}\). QPT is then shorthand for the following requirement: there exists some polynomial \(p({\sf{\lambda}})\) such that for all \({\sf{\lambda}}\in\mathbb{N}\),

1. \(\mathcal{A}_{\sf{\lambda}}\) terminates, and

2. \(\sum_{(L,t)\in X_{\sf{\lambda}}}|C_{{\sf{\lambda}}}^{L,t}|\leq p({\sf{\lambda}})~.\)

3.2.0.4 Positional Protocols.

Our protocols take place between two kinds of parties: provers and verifiers. As stated above, the verifiers always consist of two parties \(\mathcal{V}_L\) and \(\mathcal{V}_R\), whose locations are publicly known to be \(-1\) and \(1\), respectively. Provers are, in general, allowed to have circuits anywhere in \([-1,1]\). The protocol typically includes a \({\sf Setup}\) operation, whose outputs are distributed between these parties unequally. We clarify this distinction, as well as other distinctions between provers and verifiers, below:

• All verifiers can:

  • Take as input some secret information \(\mathsf{sp}\) from \({\sf Setup}\), in addition to the public information \({\sf{pp}}\). In our protocols, these are both classical.

  • Send classical or quantum messages to any position \((L,t)\).

  • Send classical or quantum messages to other verifiers through private, trusted channels.

• A prover can:

  • Take as input some prover-specific information from \({\sf Setup}\). In our protocols, this will always be a quantum state \(\rho\).

  • Send classical or quantum messages to any position \((L,t)\).

  • Send classical or quantum messages between its various distributed components through private, trusted channels.

• We assume that the prover’s trajectory is a continuous function \(L(\cdot)\) with \(L(t)\in[-1,1]\) and \(\big|\frac{L(t_1)-L(t_0)}{t_1-t_0}\big|\leq 1\) for all \(t,t_0,t_1\in\mathbb{R}^{\geq0}\). The second condition is just the speed of light constraint, as measured by the secant line of the trajectory.

The following lemma is imported from [8]. It states that no adversary can distinguish an oracle reprogramming on the position decided by the xor of random domain element sampled by \(\mathcal{V}_L,\mathcal{V}_R\) if one of the domain element hasn’t reach the adversary.

3.3 Specifying Quantum Information in Spacetime↩︎

We introduce notation, \(\mathsf{register}[\cdot](\cdot)\), for convenience in formalizing many of our extraction-based security definitions in this paper. A definition is given below.

Note that this may not correspond to a physical operation – in particular, if \(R\) contains points which are at the same spatial location at different times, these might have states which cannot physically coexist – but we still allow this to be defined for notational convenience. Also, when convenient, we will use the notation “\(S~@~t\)”, where \(S\) is a spatial region and \(t\) a time, to refer to the spacetime region \(S\times\{t\}\).

3.4 Compressed Oracle↩︎

In this subsection, we recall the technique introduced by Zhandry [34]. For more details please refer to [34]. The following part is adapted from [36]. We will show two equivalent oracle forms: the standard oracle and the compressed oracle. Note that Fourier basis is considered in other papers that use this technique but here we use Hadamard basis instead for simplicity.

We first model an oracle quantum algorithm. It consists of the following registers:

• \(\mathbf{X}\) is the register that stores either a oracle query or an answer waiting to be written.

• \(\mathbf{U}\) is the register that stores the oracle’s response or is used to store phase for the output process (will explain later).

• \(\mathbf{W}\) is the register that stores as ancilla qubits in the computation.

3.4.0.1 Standard oracle.

Let \(\mathcal{O}:\mathbb{F}_2^n \rightarrow \mathbb{F}_2^m\) be a random oracle. We can view an algorithm that runs in the random oracle model with respect to \(\mathcal{O}\) as the algorithm itself concatenated with a random oracle register \(\mathbf{D}\) that is initialized to \(\sum_{\mathcal{O}}\left|\mathcal{O}\right\rangle\left\langle\mathcal{O}\right|_{\mathbf{D}}\) (ignoring the normalizing factor). The register \(\mathbf{D}\) stores the random function \(\left|\mathcal{O}\right\rangle_{\mathbf{D}} = \left|\mathcal{O}(0^n)\right\rangle \left|\mathcal{O}(0^{n-1}1)\right\rangle \cdots \left|\mathcal{O}(1^n)\right\rangle\). The oracle unitary \({\sf StO}\) can be written as follows: \[\begin{align} {\sf StO}\left|x\right\rangle_{\mathbf{X}} \left|u\right\rangle_{\mathbf{U}} \left|w\right\rangle_{\mathbf{W}} \otimes \left|\mathcal{O}\right\rangle_{\mathbf{D}} = \left|x\right\rangle_{\mathbf{X}} \left|u + \mathcal{O}(x)\right\rangle_{\mathbf{U}} \left|w\right\rangle_{\mathbf{W}} \otimes \left|\mathcal{O}\right\rangle_{\mathbf{D}}, \end{align}\] The following lemma shows that the output distribution using a standard oracle is exactly the same as using a random oracle.

Compressed oracle.

The compressed oracle can be viewed a type of lazy sampling technique. Instead of initializing \(\mathcal{O}\) at the very beginning, the compressed oracle creates a database \(\left|D\right\rangle_{\mathbf{D}}=\left|D(0^n)\right\rangle_{\mathbf{D}_{0^n}}\left|D(0^{n-1}1)\right\rangle_{\mathbf{D}_{0^{n-1}1}}\cdots\left|D(1^n)\right\rangle_{\mathbf{D}_{1^n}}\) where \(D(x)\in\mathbb{F}_2^m\cup\left\{\bot\right\}\) and \(\left|D\right\rangle\) is initialized to \(\left|\emptyset\right\rangle_{\mathbf{D}}=\left|\bot, \bot, \cdots, \bot\right\rangle\) where \(\bot\) is a symbol that indicates the lack of information of the algorithm on certain function value. Let \(|D|\) denote the number of entries in \(D\) that are not \(\bot\). The database is initialized as an empty list \(D_0\) of length \(N\), in other words, it is initialized as the pure state \(\left|\emptyset\right\rangle := \left|\bot, \bot, \cdots, \bot\right\rangle\). Let \(|D|\) denote the number of entries in \(D\) that are not \(\bot\).

For any \(D\) and \(x\) such that \(D(x) = \bot\), we define \(D \cup (x, u)\) to be the database \(D'\), such that for every \(x' \ne x\), \(D'(x') = D(x)\) and at the input \(x\), \(D'(x) = u\).

The compressed oracle is the unitary \({\sf CStO}:= {\sf StdDecomp}\cdot {\sf CStO}' \cdot {\sf StdDecomp}\), where

• \({\sf CStO}'\) writes \(D(x)\) to the answer register \(\mathbf{U}\) by writing \(u+ D(x)\) into it when \(D(x)\neq \bot\) as usual but does nothing when \(D(x)=\bot\). Or to say that we can define addition for \(\bot\): \(u+\bot=u\), \(\forall u\in\mathbb{F}_2^m\). Formally, \[{\sf CStO}'\left|x\right\rangle_{\mathbf{X}}\left|u\right\rangle_{\mathbf{U}}\left|w\right\rangle_{\mathbf{W}}\otimes\left|D\right\rangle_{\mathbf{D}} = \left|x\right\rangle_{\mathbf{X}}\left|u+ D(x)\right\rangle_{\mathbf{U}}\left|w\right\rangle_{\mathbf{W}}\otimes\left|D\right\rangle_{\mathbf{D}}.\]

• When the algorithm queries, the database calls \({\sf StdDecomp}\) which unfolds the database and samples a value \(y\) for positions that the algorithm does not know what the value is. More specifically, \({\sf StdDecomp}\left|x\right\rangle_{\mathbf{X}}\left|u\right\rangle_{\mathbf{U}}\left|w\right\rangle_{\mathbf{W}}\otimes\left|D\right\rangle_{\mathbf{D}} := \left|x\right\rangle_{\mathbf{X}}\left|u\right\rangle_{\mathbf{U}}\left|w\right\rangle_{\mathbf{W}}\otimes{\sf StdDecomp}_x\left|D\right\rangle_{\mathbf{D}}\), where \({\sf StdDecomp}_x\) works on \(\mathbf{D}_x\).

  • If \(D(x) = \bot\), \({\sf StdDecomp}_x\) maps \(\left|\bot\right\rangle\) to \[\frac{1}{\sqrt{N}} \sum_{y\in\mathbb{F}_2^m} \left|y\right\rangle.\]

  • If \(D(x) \ne \bot\), \({\sf StdDecomp}_x\) works on the \(x\)-th register, and it is an identity on \[\frac{1}{\sqrt{N}} \sum_{y\in\mathbb{F}_2^m} (-1)^{\langle u,y\rangle} \left|y\right\rangle\] for all \(u \ne 0\); it maps the uniform superposition \(\frac{1}{\sqrt{N}} \sum_{y\in\mathbb{F}_2^m} \left|y\right\rangle\) to \(\left|\bot\right\rangle\).

    More formally, for a \(D'\) such that \(D'(x) = \bot\), \[\begin{align} {\sf StdDecomp}_x \frac{1}{\sqrt{N}} \sum_{y\in\mathbb{F}_2^m} (-1)^{\langle u,y\rangle} \left|D' \cup (x, y)\right\rangle_{\mathbf{D}} = \frac{1}{\sqrt{N}} \sum_{y\in\mathbb{F}_2^m} (-1)^{\langle u,y\rangle} \left|D' \cup (x, y)\right\rangle_{\mathbf{D}} \end{align}\] for any \(u\ne 0\) and, \[\begin{align} {\sf StdDecomp}_x \frac{1}{\sqrt{N}} \sum_{y\in\mathbb{F}_2^m} \left|D' \cup (x, y)\right\rangle_{\mathbf{D}} =\left|D'\right\rangle_{\mathbf{D}}. \end{align}\]

  Intuitively, it swaps a uniform superposition \(\frac{1}{\sqrt{N}} \sum_{y\in\mathbb{F}_2^m} \left|y\right\rangle\) with \(\left|\bot\right\rangle\) on \(\mathbf{D}_x\) and does nothing on other orthogonal basis. So it is a well defined unitary.

Note that the compressed oracle can be implemented in an efficient way where we don’t create \(\mathbf{D}_x\) for all \(x\) and we only store all non-\(\bot\) entries. For more details, please refer to [34]. Zhandry proves that, \({\sf StO}\) and CStO are perfectly indistinguishable to any unbounded quantum algorithm.

4 The Quantum Anchor State↩︎

In this section we introduce the quantum anchor state, a structured bipartite quantum state that will serve as a basic primitive throughout the paper. Intuitively, the generation process starts from several \({\sf EPR}\) pairs shared between two registers \(\text{\faAnchor}\) and \(\text{\faShip}\). Some ‘decoy’ qubits are then tensored to the \(\text{\faShip}\) register. A random unitary \(U_{\sf shift}\) is applied to \(\text{\faShip}\) to ‘scramble’ and hide the entanglement among all qubits in \(\text{\faShip}\). This ensures that once \(\text{\faShip}\) is given to another party who does not know \(U_{\sf shift}\), it cannot separate the part of \(\text{\faShip}\) that is entangled with \(\text{\faAnchor}\) from the other ‘decoy’ qubits.

If not specified, in remaining paragraphs we consider vectors and matrices with elements in \(\mathbb{F}_2\). Normally, we use \(\mathcal{O}_S^b\), where \(S\) is a set of elements (subsets, cosets, subspaces) and \(b\) is any object (such as symbols, bit strings, and field elements), to denote the oracle that outputs \(b\) on input \(x\in S\) and outputs \(\bot\) otherwise. When \(b=\top\), it is called a membership oracle and we write \(\mathcal{O}_S\) for simplicity. Also, if not specified, the domain of \(\mathcal{O}_S^b\) is the natural domain depending on \(S\). For example, when \(S\) is a subset/coset/subspace of \(\mathbb{F}_2^n\), then the domain is \(\mathbb{F}_2^n\). We abuse notations like \(\left\{0,1\right\}^n\) here so they can interact with field element such as \(x\in\mathbb{F}_2^n\). For example, we use \(0^n\times x\) to denote a vector in \(\mathbb{F}_2^{2n}\) with its first \(n\) bits all zeros and its last \(n\) bits being \(x\). Another example is that we use \(U_{\sf shift}(0^n\times S)\), where \(S\) is a subset/coset/subspace of \(\mathbb{F}_2^n\) and \(U_{\sf shift}\) is a change of basis matrix, to denote the subset/coset/subspace of \(\mathbb{F}_2^{2n}\) consisting of all vectors of the form \(U_{\sf shift}(0^n\times x)\) for \(x\in S\).

The generation process creates the following state on \(\text{\faAnchor}\text{\faShip}\): \[\propto\sum_{x\in\mathbb{F}_2^{n_e}}\left|x\right\rangle_{\text{\faAnchor}}\sum_{s\in S}(-1)^{\left \langle {s,u} \right \rangle}\left|s+U_{\sf shift}\left(0^{n_h}\times x\times 0^{n_s} \right)+v\right\rangle_\text{\faShip}.\]

\({\sf GenAnchorState}\) and \({\sf DomainExtension}\) are shown in 5.

Here are some useful facts that we will use later in the proof.

5 Collapsing vs Non-collapsing Oracles↩︎

Let \(a({\sf{\lambda}})\leq b({\sf{\lambda}})< c({\sf{\lambda}})\leq d({\sf{\lambda}})\) be polynomials of \({\sf{\lambda}}\). Let \(W\leq\mathbb{F}_2^d\) be a subspace of dimension \(c\). Let \(U^{(\cdot)}\) be any efficient isometry with superposition access to a classical oracle. We introduce a subspace oracle indistinguishability lemma below. In the remaining part of this section \(S,T\) are sampled so that \(T\leq W\) is a uniform random subspace of dimension \(b\) and \(S\leq T\) be a uniform random subspace of dimension \(a\).

Let \(m({\sf{\lambda}})\) be a polynomial. Now we consider the case that \(c=d\) and let \(w\) be a uniform random vector in \(\mathbb{F}_2^c\). We further define some oracles:

• \(\mathcal{O}_{\sf any}:\mathbb{F}_2^{c}\rightarrow\mathbb{F}_2^m\) be an oracle that is sampled from a distribution depending on \(S,T,w\) such that the every output alone is independent of \(T\) given \(S,w\). (But maybe with two outputs of inputs, one can recover \(S,T,w\))

• \(\mathcal{O}_{T+w}^{\sf ncol}:\mathbb{F}_2^{c}\rightarrow\mathbb{F}_2^{c}\cup\left\{\bot\right\}\) on input \(z\) checks if it is in \(T+w\). It returns \(\bot\) if it is not. Otherwise, it returns \(\mathcal{O}_{\sf any}({\sf Can}_S(w))\).

• \(\mathcal{O}_{T+w}^{\sf col}:\mathbb{F}_2^{c}\rightarrow\mathbb{F}_2^{c}\cup\left\{\bot\right\}\) on input \(z\) checks if it is in \(T+w\). It returns \(\bot\) if it is not. Otherwise, it returns \(\mathcal{O}_{\sf any}({\sf Can}_S(z))\).

6 Monogamy-of-Entanglement Games↩︎

The purpose of this section is to prove properties of the following game.

The main result of this section is 11. Intuitively, it states that any adversary passing the above game with good probability has to recover the value of \(b_0\) by querying its oracle already at the time BeforeSplit. Formally, we show that for each value of \(b_0\), the states corresponding to \(b_0\) at BeforeSplit are almost orthogonal to each other. Our proof establishing this fact will involve several reductions between various monogamy-of-entanglement games.

6.1 Asymmetric Monogamy-of-Entanglement Games↩︎

Now we present a modified version of the above game where the prover can choose to abort before the test.

Intuitively, \(\left|A_{s,t}\right\rangle\) and \(\left|\Psi^{\sf sk}_{0,n/2,n/2}\right\rangle\) have the same distribution. The coset state is exactly the anchor state with \(n_e=0,n_h=n_s=n/2\). We can use this theorem to prove a similar statement in our case.

Now we switch from the Goldreich-Levin style query to the oracle style query.

6.2 Multi-Stage Monogamy-of-Entanglement Games↩︎

7 Entanglement Extraction↩︎

7.1 Extracting Incompatible Measurement Results via Collapsing Oracles↩︎

In later sections, we consider \(n_e(\lambda)=n(\lambda)\) if not specified.

Now we look at a similar game DualMultiStageSearchMonogamy that reverse the order of cosets given in the challenge.

7.2 Entanglement Rigidity in Multi-Stage Monogamy-of-Entanglement Games↩︎

Define the Pauli operators \[\sigma_X= \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} \quad \sigma_Y= \begin{pmatrix} 0 & -i\\ i & 0\\ \end{pmatrix} \quad \sigma_Z= \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ \end{pmatrix}\]

8 Warmup: Localizing Entanglement in the High-Success-Probability Regime↩︎

In this section, we present a warmup to the main results of the paper — a protocol allowing us to localize EPR-pair halves to within some small region of spacetime, built and proven secure using the techniques developed in the previous sections. This is a simplified variant of the entanglement localization protocol in 9.1, with the latter being a sequentially repeated version of the former. Sequential repetition will allow us to amplify extraction fidelity, even in the low-success-probability regime.

The definition and subsequent construction in this section will have a weaker form of extraction soundness than in the main result. In 9.1, we give a stronger, more general definition accompanied by a construction which satisfies it, needing no additional assumptions.

9 Localizing Quantum Information↩︎

In this section, we present our formal definitions and constructions of the localization primitives mentioned in the introduction: entanglement localization, trajectory verification, state localization, and functionality localization. These definitions will have a stronger extraction soundness condition than was shown in the warmup, which is much more meaningful against low-success-probability adversaries. To achieve this stronger soundness, our constructions in this section employ a sequential repetition technique — each protocol is the sequential chaining of \(O(\gamma)\)-many two-round protocols.

9.1 Entanglement Localization↩︎

9.2 Trajectory Verification↩︎

Now we present a construction for trajectory verification.

9.3 State Localization↩︎

Note that in the entanglement localization scheme, if we ignore register \(\mathbf{A}\), then we are localizing the reduced state on register \(\mathbf{B}\). This idea extends to the concept of state localization.

Before coming to the proof, we give two examples of state families that are covered by our theorem. Note that we can write any \(\mathcal{S}\) from the above theorem statement as \[\mathcal{S} = \bigcup_{U \in \mathcal{U}}\left\{U\left|x\right\rangle\right\}_{x \in \{0,1\}^n}\] for some set of unitaries \(\mathcal{U}\).

• BB84 states: \(\mathcal{U}\) is the set of \(n\)-qubit unitaries \(H^{\theta_1} \otimes \dots \otimes H^{\theta_n}\) for each \(\theta \in \{0,1\}^n\).

• Coset states: \(\mathcal{U}\) is the set of unitaries that first map \(\left|x\right\rangle \to \left|Bx\right\rangle\) for some full rank \(B \in \mathbb{F}_2^{n \times n}\) and then apply \(H\) to the final \(n/2\) qubits.

9.4 Functionality Localization↩︎

We first recall the notion of quantum copy-protection from [11]. Our definition of functionality localization, stated later, will be a strengthening of copy-protection.

We also recall quantum state obfuscation, which will be used later on for our construction of functionality localization. The following definition is adapted from [20], but for simplicity we have significantly weakened the definition to work only for classical functionalities.

Now we state the main definition of this section, and present our construction of it from quantum state obfuscation and signatures.

10 Discussion↩︎

10.1 Publicly-Verifiable Localization↩︎

All of our constructions in 9 utilize some secret parameters \(\mathsf{sp}\) generated by \({\sf Setup}\) and then held privately by the verifiers. The purpose of \(\mathsf{sp}\) is, generally speaking, to serve as a verification key for the protocol – i.e. the eventual accept/reject decision is a deterministic predicate of two things, 1. the (classical) protocol transcript and 2. the secret parameters \(\mathsf{sp}\). It is natural to see if these can be made public, a la publicly-verifiable digital signatures. However unfortunately, in our constructions \(\mathsf{sp}\) contains the coset descriptors \(u,v\) – meaning that a prover knowing \(\mathsf{sp}\), even if he completely discards \(\rho\), could respond to all challenges perfectly, nullifying any extraction guarantees.

An optimistic reader might hope for alternative solutions, and therefore ask:

Are there sound localization schemes in which the verifiers hold no secret information? I.e., schemes where anyone can play the role of the verifiers, and achieve an extraction guarantee?

In this section, we will argue that we can indeed achieve this for entanglement localization, state localization, and trajectory verification, by making a slight modification to our existing constructions. Firstly, we introduce the formal notion of public verifiability.

Next, we will show an idea for how to augment our constructions of each aforementioned localization scheme, so that the verifiers can check the protocol transcript without knowledge of \(u,v\). In order to give the general idea and intuition without getting too deep into the implementation details for each specific protocol, we will keep this explanation relatively high-level.

10.1.1 Applications to Black-Box Trajectory Verification↩︎

Aside from being an interesting and desirable property on its own, public verifiability of localization protocols has a secondary benefit: allowing trajectory verification to be constructed in a relatively black-box way from a state or entanglement localization protocol. The construction is simple: run \({\sf Setup}\) as normal, and then execute back-to-back instances of \(\mathsf{Localize}\) for each checkpoint along the trajectory. The details are somewhat tedious, so we will argue about this construction at a very high level.

For completeness to hold, we must be careful that completeness of the localization protocol still holds when the prover is moving along the trajectory rather than staying in place (a la 11), and that non-destructiveness of \(\mathsf{Localize}\) applies over a short enough timescale such that the prover’s state \(\rho\) can be plugged into the next instance right away.

As for soundness, public verifiability allows for a simple black-box reduction: given an adversary for trajectory verification, simulate rounds 1 through \(i\) via the public verification algorithm. Then, forward the real \(\mathsf{Localize}\) challenges to the adversary for the given round, which it should win with high probability.

10.2 Position-Based Cryptography↩︎

Position-based authentication (PBA) is a position-based cryptographic primitive that naturally extends plain position verification, and was initially introduced together with the original construction of QPV, in Buhrman et al. ([3]). In a PBA protocol, the honest prover decides on a message \(m\) to relay to the verifiers, and the security guarantee is twofold: 1. When the honest prover is positioned in the secure location, no coalition of malicious parties located elsewhere can successfully tamper with the authenticated message, and 2. A coalition of parties with nobody in the secure location cannot pass the authentication protocol, regardless of the message. The applications of such a scheme are quite numerous and natural, e.g. authenticating military orders from a secure command center, arguably even more so than for plain position verification. As for building PBA, [3] gave a construction based on any black-box quantum position verification scheme, and Unruh showed that their QROM \(f\)-BB84 position verification scheme could be straightforwardly extended to a PBA scheme secure against all QPT attackers in the QROM ([8]).

However, we will now point out that the security notion described above, under which all PBA schemes from prior literature are proven secure, seems unsatisfying when put under scrutiny. Points 1 and 2 above rule out attacks where nobody is in the secure location, or where the honest prover algorithm runs in the presence of malicious tampering parties, but does not rule out attacks where there might be a distributed attack involving a (potentially unwitting) party in the secure location. In particular, the distributed attack on \(f\)-BB84 described in 1.5 (and depicted in 2) is an example of such an attack on the PBA scheme of Buhrman et al., when their scheme is instantiated with the \(f\)-BB84 QPV scheme.

10.2.1 An explicit “attack” scenario↩︎

We briefly describe an adversarial strategy for the PBA construction of [3], which does not constitute an attack according to the standard security definition, but is nonetheless a concerning scenario for any real-world application of PBA. To describe this attack we’ll first give a summary of their construction.

Intuitively, this protocol is secure in their model because if nobody is at the purported location, then indeed there is nothing a malicious prover can do to inject 1s into the encoding of the message. Injecting 0s is easier, since anyone can send \(\bot\), but the encoding prevents this from ever succeeding to tamper with the true message bit.

We now get to describing our “attack”. Imagine that there are three provers, \(P_L,P_M,P_R\), where only \(P_M\) is at the true location. They participate in the scheme of 54 where the QPV scheme is \(f\)-BB84, and have the following strategy. Say, without loss of generality, that the BB84 qubit comes from the left.

• \(P_L\) and \(P_R\) pre-determine a message bit \(c\in\{0,1\}\). They compute the encoding \({\sf Enc}(c)\), and execute the following strategy for each index \(i\) of the encoded string:

  1. When \(P_L\) receives the qubit \(H^\theta\left|b\right\rangle\), it applies a quantum one-time pad \(X^rZ^s\), where the one-time pad key \((r,s)\) belongs to private shared randomness of \(P_L\) and \(P_R\). Importantly, \(P_M\) never sees this key. \(P_L\) forwards the scrambled qubit to \(P_M\).

  2. When \(P_M\) receives the qubit, it measures in the correct basis determined by the \(f\)-BB84 challenges. It sends the measurement outcome \(b'\) to \(P_L\) and \(P_R\).

  3. \(P_L\) and \(P_R\) receive this measurement outcome, and by this time they also have full knowledge of the \(f\)-BB84 challenges. Namely, they know which basis the middle prover measured in, and thus which correction to apply from the quantum one-time pad in order to find the intended measurement outcome \(b\).

  4. If \(m_i=1\), then \(P_L\) and \(P_R\) send the outcome \(b\) to their respective nearest provers. Otherwise, if \(m_i=0\), then with probability \(q\) they instead send \(\bot\) to each prover.

It is clear that this attack would not violate the typical security definition, since it involves active participation from a prover \(P_M\) who is in the secure location. However, there is a very concerning property of this scheme – namely, that \(P_M\) is entirely unaware of the message being authenticated. In other words, there might be a prover in the right location who was simply tricked into participating, and the authenticated message in no way originates from the secure location.

10.2.2 Towards stronger security notions↩︎

To address this attack, we give some informal directions for tackling this weakness in the security definition of PBA. We propose that the localization techniques developed in this paper, for example that of functionality localization, could be used to rule out this class of cheating strategies where the middle prover is acting blindly, without knowledge of the message.

A concrete idea is the following (informal) PBA scheme:

• Let \(\mathcal{F}=\{f_k\}_k\) be a PRF. Take \(({\sf Setup},\mathsf{Localize},{\sf Eval})\) from the functionality localization scheme in 43 instantiated for \(\mathcal{F}\). Let \(H\) be a public random oracle.

• The verifiers run \({\sf{pp}},\mathsf{sp},f_k,\rho\gets{\sf Setup}(1^\lambda)\), and send \({\sf{pp}},\rho\) to the prover. Next, they sample two random challenge strings \(c_L,c_R\in\{0,1\}^{\sf{\lambda}}\).

• Two routines are executed simultaneously:

  • The prover and verifiers execute \[\mathsf{Localize}\big( P(\rho) \rightleftharpoons V(\mathsf{sp},f)\big)({\sf{pp}},L,t)\]

  • The left and right verifiers send \(c_L\) and \(c_R\), respectively, towards \((L,t)\). The prover receives these, computes \(c:=c_L\oplus c_R\) and runs \(y\gets{\sf Eval}(\rho,H(m||c))\). The prover sends \((m,y)\) to both verifiers simultaneously.

• The verifiers accept iff \(\mathsf{Localize}\) accepted and \(y=f_k(H(m||(c_L\oplus c_R)))\).

Intuitively, the point of this construction is to authenticate the prover’s message with the copy-protected PRF, which is simultaneously being localized to a single position. If a group of provers pass this protocol with high probability, then soundness of functionality localization guarantees that we can extract the ability to sign (say, uniformly random) messages from the circuits at the secure location. Uniqueness also guarantees that this cannot be happening anywhere else at time \(t\). Thus, when the verifiers receive the signed message \(m,f_k(H(m||c))\), we know that this evaluation must have taken place locally at the secure location, which additionally tells us that the prover queried the oracle value \(H(m||c)\) at this location at time \(t\). The techniques from our localization constructions would then allow this query to be recorded and “extracted” from the prover’s circuitry at that position.

We leave further exploration of this direction to future work, e.g. formalize a stronger notion of security for position-based authentication and analyze the above construction in terms of said notion.

References↩︎

---

1. We provide more details about this model, which is sometimes referred to as the classical oracle model, in 1.4.↩︎

2. Technically, \(H\) will be implemented by a pseudorandom function so that the oracle \(\mathcal{O}\) is efficiently computable.↩︎

3. One way to check this is to have the verifiers remember a secret verification key \({\sf sk}= (u,v)\) consisting of the shifts and have them query \({\mathcal{O}}(a \oplus b,v)\) and \({\mathcal{O}}(a \oplus b,u)\).↩︎

4. For technical reasons, our actual protocol is slightly more elaborate than this, where the standard- and Hadamard-basis queries are sequentially staggered (by a tiny time difference). We elaborate more on this in 2.↩︎

5. Again, the actual trajectory verification protocol we construct is slightly different, for technical reasons.↩︎

6. We note that the description of this game is slightly inaccurate, and we refer the reader to 6, and in particular 9, for formal details.↩︎

7. We note that one could alternatively specify that the verify sent strictly alternating challenges, but this requires it to keep some state in between each challenge, which may be undesirable.↩︎

8. Technically, we say that a functionality is “copy-protectable” if there exists some distribution \(\mathcal{D}\) over inputs such that \(\mathcal{F}\) is copy-protectable with respect to independent challenges \(x_0,x_1\) sampled from \(\mathcal{D}\). See 9.4 for more details.↩︎

9. It is natural to ask whether our protocols can be extended to work in standard three-dimensional space. We expect that, similarly to [8], there is a natural generalization to three dimensions which can be then compiled to a more abstracted causal circuit, and analyzed without dealing with three-dimensional geometry. However, we leave this generalization as an open problem.↩︎

10. This restriction is without loss of generality. Since we assume – as is standard in QPV literature – that all computation is instantaneous, any computation which is being done locally at one cell, whether the cell is stationary or moving, can always be freely pushed forward or backward to the nearest intersection points with other cells.↩︎

11. In general, we should allow any quantum verifier. Nevertheless, our construction achieves classical verification.↩︎

12. In reality, we localize a family of bipartite states indexed by \({\sf{\lambda}}\), i.e. \(\Sigma=\{\sigma_{\sf{\lambda}}\}_{\sf{\lambda}}\). As is standard in these contexts, we suppress the dependence on \({\sf{\lambda}}\) for notational convenience, and simply write \(\sigma\).↩︎

13. Technically, a sequence of states indexed by \({\sf{\lambda}}\) – see 12.↩︎

14. To enable extraction from all points along the trajectory, we must send a round of challenges after* the prover has already reached the endpoint \((L(\tau),\tau)\). We define the extension \(\widetilde{L}\) for notational convenience when sending these post-trajectory challenges.*↩︎

15. Technically, we have one state family per security parameter \({\sf{\lambda}}\) – see 12↩︎

16. It is crucial that this extractor does not know \(i\).↩︎

17. In this purified version, the family of states is indexed by \(U,x\). There is a one-to-one correspondence between \(U,x\) and, \(i\) which we used in the original definition.↩︎

18. Technically, we have one function family per security parameter \({\sf{\lambda}}\) – see 12↩︎

19. We leave out functionality localization from this statement, because it is unclear how public verifiability should be defined with respect to the private functionality \(f\). If \(f\) itself has a natural notion of public verification (e.g. if \(f\) is a copy-protectable signing algorithm for a public-key signature scheme), then we could potentially hope to extend the techniques in this section to allow such a functionality \(f\) to be localized in a publicly verifiable way.↩︎