Quantum Position Verification: Loss-tolerant Protocols and Fundamental Limits
Philip Verduyn Lunel

Abstract:
This thesis explores position-based quantum cryptography zooming in on the task of position verification. In position verification, the idea is to use an individual's geographical location as a cryptographic credential. Practically, such protocols can authenticate that a message originated from a specific location or ensure that messages can only be read at a certain location.

In a position-verification protocol, the limitations imposed by the speed of light, as described by special relativity, are used to verify that a party is at their claimed location. This task has been shown to be impossible to implement using only classical information. Initially, the hope was that using quantum information we could construct secure quantum position verification (QPV) protocols. However, it has been shown that any QPV protocol can be broken by attackers that use an amount of entanglement exponential in the input size.

Thus, unconditionally-secure quantum position-verification protocols do not exist. However, from a practical point of view, not all is lost. The exponential upper bound for a general attack is still astronomically large for only a relatively small input. Thus, we can still hope for practically secure QPV protocols. This raises the problem of designing protocols that are secure in a practical setting. An important problem that immediately arises is that of signal loss. Signal loss can be detrimental as it allows attackers to only answer on a subset of rounds.

We propose a new protocol, QPV_SWAP, which is fully loss-tolerant against classical attackers. The task of the protocol, which could be implemented using only a single beam splitter and two detectors, is to estimate the overlap between two input states. By formulating the optimal attack as a semidefinite program (SDP), which we solve analytically, we give optimal bounds on the success probability of attackers and show that the protocol obeys strong parallel repetition.  

We then construct the first known example of a QPV protocol that is provably secure against unentangled attackers restricted to classical communication, but can be perfectly attacked by local operations and a single round of simultaneous quantum communication, indicating that allowing for quantum communication may break security. We then show that any protocol secure against classical communication can be transformed into a protocol secure against quantum communication. We further show, using arguments based on the monogamy of entanglement, that the task of Bell state discrimination cannot be done with only local operations and a single round of simultaneous quantum communication, not even when attackers are allowed to declare a loss, making this the first fully loss-tolerant QPV task secure against quantum communication attacks. We also show that the security of the Bell state discrimination protocol implies similar security for the QPV_SWAP.

An interesting QPV candidate is the QPV f-BB84 protocol, which is a QPV protocol that consists of a single qubit input with classical n-bit strings that determine the measurement basis in which the qubit has to be measured. This protocol has the desirable property that the entanglement needed to attack the protocol scales with the size of the classical information. However, the protocol can be trivially broken for loss rates higher than 50%. We propose a modified structure of QPV protocols by introducing a commitment to play before proceeding, and prove that this modification makes the potentially high transmission loss between the verifiers and the prover security-irrelevant for a class of protocols that includes the QPV f-BB84. The adapted protocol c-QPV f-BB84 protocol then becomes a practically feasible QPV protocol with strong security guarantees, even against attackers using adaptive strategies. As the loss rate between the verifiers and the prover is mainly dictated by the distance between them, secure QPV over longer distances becomes possible. We also show possible feasible implementations of the required photon presence detection, making c-QPV f-BB84 protocol a protocol that solves all major practical issues in QPV. It is secure against slow quantum communication and loss, and the prover's operations are relatively simple, since he only needs to manipulate a single qubit and make a classical computation. 

We then invert the picture, and consider the task of non-local quantum computation (NLQC), which corresponds to the operations of the attackers in a QPV protocol. We connect NLQC to the wider context of information-theoretic cryptography by relating it to a number of other cryptographic primitives. We show that one special case of NLQC, known as F-routing, is equivalent to the quantum analogue of the conditional disclosure of secrets (CDS) primitive, where by equivalent we mean that a protocol for one task gives a protocol for the other with only small overhead in resource costs. We further consider another special case of position verification, which we call coherent function evaluation (CFE), and show that CFE protocols induce similarly efficient protocols for the private simultaneous message passing (PSM) scenario. By relating position-verification to these cryptographic primitives, a number of results in the information-theoretic cryptography literature give new implications for NLQC, and vice versa. These include the first sub-exponential upper bounds on the worst case cost of F-routing of 2^{O(sqrt{n\log n})} entanglement, the first example of an efficient f-routing strategy for a problem believed to be outside P/poly, linear lower bounds on quantum resources for CDS in the quantum setting, linear lower bounds on communication cost of CFE, and efficient protocols for CDS in the quantum setting for functions that can be computed with quantum circuits of low T depth.