In this article, we propose quantum position verification (QPV) schemes where all the channels are untrusted except the position of the prover and distant reference stations of verifiers. We review and analyze the existing QPV schemes containing some pre-shared data between the prover and verifiers. Most of these schemes are based on non-cryptographic assumptions, i.e. quantum/classical channels between the verifiers are secure. It seems impractical in an environment fully controlled by adversaries and would lead to security compromise in practical implementations. However, our proposed formula for QPV is more robust, secure and according to the standard assumptions of cryptography. Furthermore, once the position of the prover is verified, our schemes establish secret keys in parallel and can be used for authentication and secret communication between the prover and verifiers.
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.
Abstract Quantum position verification (QPV) enables multiple verifiers to certify a prover’s location using quantum communication and physical assumptions. With experimental demonstrations of QPV becoming increasingly feasible, enhancing the practicality and security of QPV protocols is more important than ever. In this work, we make three key contributions toward this goal. First, we introduce a robust QPV protocol in which the verifier’s state preparation is independent of channel loss, improving reliability in real-world conditions. Second, we refine existing security analysis techniques to bolster protocol resilience against experimental imperfections. Third, we identify and address some implicit assumptions present in existing security analyses, providing a framework to eliminate such assumptions. Additionally, as an example of QPV application beyond location verification, we illustrate how QPV can be leveraged for authenticating classical communication in quantum key distribution.
Position verification is an emerging field of quantum cryptography. Its goal is to verify whether a distant communicating party is telling the truth about where they are. However, the problem is usually formulated in a way that the position is the only credential of that party, which cannot guarantee uniqueness. In this study, the authors show how a practically secure position verification algorithm – assuming it exists – might be used to track (i.e. repeatedly verify the position) of some unique key or cipher text. To achieve this, they rely on pre‐prepared position verification data called trackers. They also propose three algorithms that implement their general tracking scheme and examine some questions related to their security. These implementations include shuffling trackers into valuable data and hiding their memory address through a random permutation; using CNOT operations to entangle valuable data and trackers; and using random qubit strings from which either trackers or secret keys can be produced at will. These methods may be used to track a diplomatic package or reveal the location of a malicious party during a denial of service attack.
Quantum cryptography and quantum search algorithm are considered as two important research topics in quantum information science. An asymmetrical quantum encryption protocol based on the properties of quantum one-way function and quantum search algorithm is proposed. Depending on the no-cloning theorem and trapdoor one-way functions of the public-key, the eavesdropper cannot extract any private-information from the public-keys and the ciphertext. Introducing key-generation randomized logarithm to improve security of our proposed protocol, i.e., one private-key corresponds to an exponential number of public-keys. Using unitary operations and the single photon measurement, secret messages can be directly sent from the sender to the receiver. The security of the proposed protocol is proved that it is information-theoretically secure. Furthermore, compared the symmetrical Quantum key distribution, the proposed protocol is not only efficient to reduce additional communication, but also easier to carry out in practice, because no entangled photons and complex operations are required.
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