Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1507.00626 · Physical Review A

Practical position-based quantum cryptography

Kaushik Chakraborty, Anthony Leverrier

Published Nov 5, 2015• 50 citations
arXivHTMLPDF

Abstract

We study a general family of quantum protocols for position verification and present a class of attacks based on the Clifford hierarchy. These attacks outperform current strategies based on port-based teleportation for a large class of practical protocols. We then introduce the interleaved product protocol, a scheme for position verification involving only the preparation and measurement of single qubit states for which the best available attacks have a complexity exponential in the number of classical bits transmitted.

DOI
10.1103/physreva.92.052304

Related papers

Attack strategies for position-based quantum cryptography based on the Clifford Hierarchy

Kaushik Chakraborty, Anthony Leverrier

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

•Jun 4, 2015•1 citation

Practically secure quantum position verification

Siddhartha Das, George Siopsis

Abstract We discuss quantum position verification (QPV) protocols in which the verifiers create and send single-qubit states to the prover. QPV protocols using single-qubit states are known to be insecure against adversaries that share a small number of entangled qubits. We introduce QPV protocols that are practically secure: they only require single-qubit states from each of the verifiers, yet their security is broken if the adversaries sharing an impractically large number of entangled qubits employ teleportation-based attacks. These protocols are a modification of known QPV protocols in which we include a classical random oracle without altering the amount of quantum resources needed by the verifiers. We present a cheating strategy that requires a number of entangled qubits shared among the adversaries that grows exponentially with the size of the classical input of the random oracle.

arXiv:1711.03392•New Journal of Physics•Jun 1, 2021•11 citations

Breaking simple quantum position verification protocols with little entanglement

Andrea Olivo, Ulysse Chabaud, André Chailloux +1 more

Instantaneous nonlocal quantum computation (INQC) evades apparent quantum and relativistic constraints and allows to attack generic quantum position verification (QPV) protocols (aiming at securely certifying the location of a distant prover) at an exponential entanglement cost. We consider adversaries sharing maximally entangled pairs of qudits and find low-dimensional INQC attacks against the simple practical family of QPV protocols based on single photons polarized at an angle $θ$. We find exact attacks against some rational angles, including some sitting outside of the Clifford hierarchy (e.g. $π/6$), and show no $θ$ allows to tolerate errors higher than $\simeq 5\cdot 10^{-3}$ against adversaries holding two ebits per protocol's qubit.

arXiv:2007.15808•Jul 31, 2020•11 citations

Position-based quantum cryptography: from theory towards practice

Rene Allerstorfer

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.

•Jan 1, 2024•0 citations

Position-Based Quantum Cryptography and the Garden-Hose Game

Florian Speelman

We study position-based cryptography in the quantum setting. We examine a class of protocols that only require the communication of a single qubit and 2n bits of classical information. To this end, we define a new model of communication complexity, the garden-hose model, which enables us to prove upper bounds on the number of EPR pairs needed to attack such schemes. This model furthermore opens up a way to link the security of position-based quantum cryptography to traditional complexity theory.

arXiv:1210.4353•Oct 16, 2012•10 citations

Quantum position verification: loss-tolerant protocols and fundamental limits

Philip Verduyn Lunel

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.

•Jan 1, 2024•0 citations
We study a general family of quantum protocols for position verification and present a class of attacks based on the Clifford hierarchy. These attacks outperform current strategies based on port-based teleportation for a large class of practical protocols. We then introduce the interleaved product protocol, a scheme for position verification involving only the preparation and measurement of single qubit states for which the best available attacks have a complexity exponential in the number of classical bits transmitted.
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
Abstract We discuss quantum position verification (QPV) protocols in which the verifiers create and send single-qubit states to the prover. QPV protocols using single-qubit states are known to be insecure against adversaries that share a small number of entangled qubits. We introduce QPV protocols that are practically secure: they only require single-qubit states from each of the verifiers, yet their security is broken if the adversaries sharing an impractically large number of entangled qubits employ teleportation-based attacks. These protocols are a modification of known QPV protocols in which we include a classical random oracle without altering the amount of quantum resources needed by the verifiers. We present a cheating strategy that requires a number of entangled qubits shared among the adversaries that grows exponentially with the size of the classical input of the random oracle.
Instantaneous nonlocal quantum computation (INQC) evades apparent quantum and relativistic constraints and allows to attack generic quantum position verification (QPV) protocols (aiming at securely certifying the location of a distant prover) at an exponential entanglement cost. We consider adversaries sharing maximally entangled pairs of qudits and find low-dimensional INQC attacks against the simple practical family of QPV protocols based on single photons polarized at an angle θθθ. We find exact attacks against some rational angles, including some sitting outside of the Clifford hierarchy (e.g. π/6π/6π/6), and show no θθθ allows to tolerate errors higher than ≃5⋅10−3\simeq 5\cdot 10^{-3}≃5⋅10−3 against adversaries holding two ebits per protocol's qubit.
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 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.