Position-based quantum cryptography (PBQC) allows a party to use its geographical location as its only credential to implement various cryptographic protocols. Such a protocol may lead to important applications in practice. Although it has been shown that any PBQC protocol is breakable if the adversaries pre-share an arbitrarily large entangled state, the security of PBQC in the bounded-quantum-storage model is still an open question. In this paper, we study the performance of various PBQC protocols over a lossy channel under the assumption that no entanglement is pre-shared between adversaries. By introducing the decoy state idea, we show that an extended Bennett-Brassard-1984--type PBQC protocol implemented with a weak coherent source and realistic single-photon detectors can tolerate an overall loss (including both the channel loss and the detection efficiency) of 13 dB if the intrinsic quantum bit error rate is 1%. We also study a few continuous variable PBQC protocols and show that they suffer from a 3-dB loss limitation.
Position-based quantum cryptography (PBQC) allows a party to use its geographical location as its only credential to implement various cryptographic protocols. Such a protocol may lead to important applications in practice. Although it has been shown that any PBQC protocol is breakable if the adversaries pre-share an arbitrarily large entangled state, the security of PBQC in the bounded-quantum-storage model is still an open question. In this paper, we study the performance of various PBQC protocols over a lossy channel under the assumption that no entanglement is pre-shared between adversaries. By introducing the decoy state idea, we show that an extended Bennett-Brassard-1984--type PBQC protocol implemented with a weak coherent source and realistic single-photon detectors can tolerate an overall loss (including both the channel loss and the detection efficiency) of 13 dB if the intrinsic quantum bit error rate is 1%. We also study a few continuous variable PBQC protocols and show that they suffer from a 3-dB loss limitation.
Quantum position verification (QPV) is the art of verifying the geographical location of an untrusted party. Recently, it has been shown that the widely studied Bennett Brassard 1984 (BB84) QPV protocol is insecure after the 3 dB loss point assuming local operations and classical communication (LOCC) adversaries. Here, we propose a time-reversed entanglement swapping QPV protocol (based on measurement-device-independent quantum cryptography) that is highly robust against quantum channel loss. First, assuming ideal qubit sources, we show that the protocol is secure against LOCC adversaries for any quantum channel loss, thereby overcoming the 3 dB loss limit. Then, we analyze the security of the protocol in a more practical setting involving weak laser sources and linear optics. In this setting, we find that the security only degrades by an additive constant and the protocol is able to verify positions up to 47 dB channel loss.
In this thesis we explore 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. In practice, 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. It has been shown that any QPV protocol can be broken by attackers that use an amount of entanglement exponential in the input size. However, from a practical point of view, not all is lost. We can still hope for QPV protocols that are secure in practice. This raises the problem of designing protocols that are secure in a practical setting. An important problem that arises is that of signal loss. Signal loss can be detrimental as it allows attackers to only answer on a subset of rounds. We investigate several questions related to the practical implementation of such protocols. We propose a new experimentally feasible protocol, which is fully loss-tolerant against attackers restricted to classical communication. Furthermore, we consider the role of allowing quantum communication with no pre-shared entanglement for attackers and show that this setting is strictly stronger than the classical one, indicating that allowing for quantum communication may break security. Conversely, we then show that any protocol secure against classical communication can be transformed into a protocol secure against quantum communication. Finally, we 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.
This thesis deals with position-based quantum cryptography (PBQC), a type of quantum cryptography. More concretely, we focus on the design and study of quantum position verification (QPV) protocols, which act as a building block for PBQC. We prioritise the development of QPV protocols that are loss-tolerant, error-robust, and feasible with current or near-future technology, concentrating on photon-based protocols and linear-optical equipment. We also theoretically study different attack settings on QPV in the context of state discrimination, dealing with the interplay between non-locality and interaction. We introduce a new QPV protocol based on the SWAP test and Hong-Ou-Mandel interference and study it in detail regarding attacks and practical feasibility. We further provide a solution to a major practical issue of QPV -- signal loss. A minor modification of the standard structure of QPV, namely introducing a small time delay and a commitment to play from the honest prover, allows us to provably make the transmission loss between the verifiers and the honest party irrelevant for security for a class of QPV protocols. Moreover, we generalise and study QPV protocols in the continuous-variable setting. Exploring theoretical aspects of QPV attacks, we focus on the difference between quantum and classical communication. We show new bounds on existing protocols, construct protocols that can be attacked with quantum communication but not locally, show a separation between quantum and classical communication attacks on QPV, and derive a necessary condition on the attack error based on the structure of the QPV input ensemble.
Quantum position verification (QPV) aims to certify the location of an untrusted prover, but faces two major obstacles: fundamentally, entanglement-based attacks and, experimentally, photon loss. A commitment-based modification introduced in Phys. Rev. Lett. 135, 260801 addresses both in sequentially repeated protocols. Its security analysis, however, relies on the sequential structure and does not extend to parallel repetition. We use a different proof approach to establish security of the commitment modification for a parallel BB84-based QPV protocol. Against bounded-entanglement adversaries, the acceptance probability decays exponentially in the minimum number k of successfully committed qubits. The protocol tolerates arbitrary transmission loss and noise rates up to 3.7%, while allowing arbitrarily slow quantum communication. This yields a fully loss-tolerant, single-execution QPV protocol secure against bounded-entanglement attacks, removing transmission loss as a fundamental limitation on verification distance. We also revisit sequential repetition, correcting the treatment of conditioning on commitment and replacing the earlier conditional guarantee with an unconditional security bound, without the finite-size correction to the correctness gap. The resulting bound provides improved quantitative security parameters for experimental implementations.
The goal of position-based cryptography is for an honest party to use her spatio-temporal position as her only credential in a cryptographic protocol. In particular, Position-Verification aims at verifying that a certain party, called the prover, holds a given position in spacetime. Such a protocol typically goes as follows: a set of verifiers will coordinate and send some challenge to the prover, and it is expected that only someone sitting in the supposed position of the prover can successfully pass the challenge. Two papers established that information theoretic security is not possible for Position-Based Quantum Cryptography (PBQC) protocols: neither in the classical [1], nor in the quantum [2] regime. More precisely, it is always possible for a coalition of adversaries to convince the verifiers, even if none of the adversary sits in the spatiotemporal region where the prover is supposed to be. At the same time, the best known attack strategies require the adversaries to share very entangled states: the attacks described in [2] are based on Vaidman’s protocol for nonlocal computation [3] and consist in the cheaters teleporting some quantum state back and forth, with a total cost in terms of required EPR pairs that scales double exponentially in n, the number of qubits involved in the PBQC protocol. Later, new generic attacks based on port-based teleportation[4] were proposed and require only exponential entanglement to succeed [5]. Finally, it is also know that a linear amount of entanglement is not su cient to break the PBQC protocol [5], [6]. A major open question in the field is to bridge the gap between lower and upper bounds: does there exist a protocol that requires exponentially many EPR pairs to break, or are all PBQC protocols insecure against a coalition of adversaries that shares polynomially many EPR pairs? While we do not settle this question in the present paper, we make some progress towards it by exhibiting new attack strategies with polynomial complexity against a large family of practical protocols. These attacks rely on teleportation gates and their precise complexity can be quantified with the notion of Cli↵ord hierarchy [7] of a quantum gate. We then introduce a new family of protocols, that generalizes a construction by Lau and Lo [8], which appears to be immune against these polynomialcomplexity attacks. Another main challenge is to determine whether there exist some PBQC protocol resistant to channel imperfections, either losses or noise, between the verifiers and
In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, the task of secure position-verification is impossible. To this end, we prove the following very general result. Assume that Alice and Bob hold respectively subsystems A and B of a (possibly) unknown quantum state ∣ψ⟩∈HA⊗HB. Their goal is to calculate and share a new state ∣φ⟩=U∣ψ⟩, where U is a fixed unitary operation. The question that we ask is how many rounds of mutual communication are needed. It is easy to achieve such a task using two rounds of classical communication, whereas, in general, it is impossible with no communication at all. Surprisingly, in case Alice and Bob share enough entanglement to start with and we allow an arbitrarily small failure probability, we show that the same task can be done using a single round of classical communication in which Alice and Bob exchange two classical messages. Actually, we prove that a relaxed version of the task can be done with no communication at all, where the task is to compute instead a state ∣φ′⟩ that coincides with ∣φ⟩=U∣ψ⟩ up to local operations on A and on B, which are determined by classical information held by Alice and Bob. The one-round scheme for the original task then follows as a simple corollary. We also show that these results generalize to more players. As a consequence, we show a generic attack that breaks any position-verification scheme. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure position-verification is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any preshared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.