Abstract In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a position verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above.
Abstract In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a position verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above.
Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary UAB by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary UAB whose implementation in NLQC requires extra quantum systems with dimensions exp(nΩ(1)), where n is the dimension of systems A and B. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in n.
In this paper we consider the family of diagonal ±1 valued unitaries Uε, indexed by an element of the Boolean hypercube ε∈{±1}n2, i.e. Uε∣i⟩A∣j⟩B=εij∣i⟩A∣j⟩B. We show that if Uε can be implemented in NLQC with constant accuracy for all ε, and the dependency on ε in the first round of the associated strategy is a polynomial of degree O(n41−δ), then the implementation of at least one Uε in NLQC requires resources scaling as exp(Ω((logn)2n2δ)). The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.
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
While it is known that unconditionally secure position-based cryptography is impossible both in the classical and the quantum setting, it has been shown that some quantum protocols for position verification are secure against attackers which share a quantum state of bounded dimension. In this work, we consider the security of two protocols for quantum position verification that combine a single qubit with classical strings of total length 2n: The qubit routing protocol, where the classical information prescribes the qubit's destination, and a variant of the BB84-protocol for position verification, where the classical information prescribes in which basis the qubit should be measured. We show that either protocol is secure for a randomly chosen function if each of the attackers holds at most n/2−5 qubits. With this, we show for the first time that there exists a quantum position verification protocol where the ratio between the quantum resources an honest prover needs and the quantum resources the attackers need to break the protocol is unbounded. The verifiers need only increase the amount of classical resources to force the attackers to use more quantum resources. Concrete efficient functions for both protocols are also given -- at the expense of a weaker but still unbounded ratio of quantum resources for successful attackers. Finally, we show that both protocols are robust with respect to noise, making them appealing for applications.
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.
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.
Position verification, introduced by Chandran et al. (SIAM J. Computing 2014), allows verifiers to test a prover's claimed position by an interactive protocol. Classical position verification is impossible. Even for Quantum Position Verification (QPV), there always exists an LOCC (Local Operations and Classical Communication) attack if the adversary can hold an exponentially large amount of preshared entanglement.
Somewhat surprisingly, we show that we can circumvent this barrier in the idealized continuous-time model, where time is represented by a real-valued parameter and challenge messages can be sent at a time sampled uniformly from a real interval. In this model, we give a BB84-based protocol that remains secure against any finite coalition of LOCC adversaries with arbitrary finite (possibly exponential) quantum storage and entanglement.
Our construction can also be instantiated in the discrete-time model. Even though the previous impossibility results apply, we are able to obtain an information-theoretic QPV protocol in which the honest parties' total resources (communication and storage) can be significantly smaller than the adversarial resource bound. In fact, we can achieve any desired polynomial gap between honest parties and adversarial resources. To our knowledge, all previous protocols in the literature required resources of the honest parties to be at least as large as the adversarial entanglement.
Interestingly, the resource gap between the honest and adversarial party resources in our protocol depends on how precisely time can be measured. As the precision of the best-known clock improves with further research, the resource gap in our protocol keeps increasing. In particular, the adversarial resource bound keeps increasing while the honest parties' resources remain largely the same. We call this the "I sleep, you work" paradigm.