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• 33 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•7 citations

Position-based cryptography: Single-qubit protocol secure against multi-qubit attacks.

Andreas Blühm, Matthias Christandl, Florian Speelman

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.

•Apr 13, 2021•2 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•3 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•5 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.
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 2n2n2n: 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−5n/2 - 5n/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.
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.