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

Lecture notes in computer science

Position-Based Quantum Cryptography: Impossibility and Constructions

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner

Published Jan 1, 2011• 59 citations
Publisher
DOI
10.1007/978-3-642-22792-9_24

Related papers

Position-Based Cryptography

Nishanth Chandran, Vipul Goyal, Ryan Moriarty +1 more

In this paper, we initiate the theoretical study of cryptographic protocols where the identity, or other credentials and inputs, of a party are derived from its geographic location. We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the vanilla (or standard) model, the above task (i.e., of secure positioning) is impossible to achieve, even if we assume that the adversary is computationally bounded. In light of the above impossibility result, we then turn to Dziembowski's bounded retrieval model (a variant of Maurer's bounded storage model) and formalize and construct information theoretically secure protocols for two fundamental tasks: secure positioning and position-based key exchange. We then show that these tasks are in fact universal in this setting---we show how we can use them to realize secure multiparty computation. Our main contribution in this paper is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results showing that the bounded-retrieval framework is a fruitful one to study the foundations of position-based cryptography.

SIAM Journal on Computing•Jan 1, 2014•13 citations

Quantum Cryptography: Principles, Implementation and Perspectives

Philippe B. Gallion

•Jun 1, 2018•0 citations

Theoretical foundations of position-based cryptography

Rafail Ostrovsky, Amit Sahai, Nishanth Chandran

In this thesis, we initiate the study of cryptographic protocols where the identity, or other credentials and inputs, of a party are derived from its geographic location. We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the Vanilla (or standard) model, this above task (i.e., of secure positioning) is impossible to achieve, even if we assume that the adversary is computationally bounded. In light of the above impossibility result, we then turn to Dziembowski's Bounded Retrieval Model (a variant of Maurer's Bounded Storage Model) and formalize and construct information theoretically secure protocols for two fundamental tasks: Secure Positioning; and Position-Based Key Exchange. We then show that these tasks are in fact universal in this setting—we show how we can use them to realize Secure Multi-Party Computation. The main contribution of this thesis is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results showing that the bounded-retrieval framework is a fruitful one to study the foundations of position-based cryptography. This thesis is based on joint works with Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky.

•Jan 1, 2011•2 citations

Quantum cryptography: from theory to practice

Eleni Diamanti

•Feb 1, 2014•3 citations

The causal structure of Minkowski space time: possibilities and impossibilities of secure positioning

Muhammad Nadeem

Secure positioning, a prover located at a specified position convinces a set of verifiers at distant reference stations that he/she is indeed at the specific position, is considered to be impossible if the prover and verifiers have no pre-shared data while dishonest provers have an arbitrary amount of pre-shared entanglement [Nature 479, 307-308 (2011)]. We argue here that current impossibility results for secure positioning are the upshot of not utilizing full powers of relativistic quantum information theory and show that secure positioning and hence position-based quantum cryptography is possible if causal structure of Minkowski space time and quantum non-locality is used properly.

arXiv:1505.01839•May 7, 2015•3 citations

Quantum cryptography and its application frontiers

Romain Alléaume

•Sep 24, 2021•0 citations
In this paper, we initiate the theoretical study of cryptographic protocols where the identity, or other credentials and inputs, of a party are derived from its geographic location. We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the vanilla (or standard) model, the above task (i.e., of secure positioning) is impossible to achieve, even if we assume that the adversary is computationally bounded. In light of the above impossibility result, we then turn to Dziembowski's bounded retrieval model (a variant of Maurer's bounded storage model) and formalize and construct information theoretically secure protocols for two fundamental tasks: secure positioning and position-based key exchange. We then show that these tasks are in fact universal in this setting---we show how we can use them to realize secure multiparty computation. Our main contribution in this paper is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results showing that the bounded-retrieval framework is a fruitful one to study the foundations of position-based cryptography.
In this thesis, we initiate the study of cryptographic protocols where the identity, or other credentials and inputs, of a party are derived from its geographic location. We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the Vanilla (or standard) model, this above task (i.e., of secure positioning) is impossible to achieve, even if we assume that the adversary is computationally bounded. In light of the above impossibility result, we then turn to Dziembowski's Bounded Retrieval Model (a variant of Maurer's Bounded Storage Model) and formalize and construct information theoretically secure protocols for two fundamental tasks: Secure Positioning; and Position-Based Key Exchange. We then show that these tasks are in fact universal in this setting—we show how we can use them to realize Secure Multi-Party Computation. The main contribution of this thesis is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results showing that the bounded-retrieval framework is a fruitful one to study the foundations of position-based cryptography. This thesis is based on joint works with Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky.
Secure positioning, a prover located at a specified position convinces a set of verifiers at distant reference stations that he/she is indeed at the specific position, is considered to be impossible if the prover and verifiers have no pre-shared data while dishonest provers have an arbitrary amount of pre-shared entanglement [Nature 479, 307-308 (2011)]. We argue here that current impossibility results for secure positioning are the upshot of not utilizing full powers of relativistic quantum information theory and show that secure positioning and hence position-based quantum cryptography is possible if causal structure of Minkowski space time and quantum non-locality is used properly.