 Author
 Year
 2014
 Title
 Positionbased quantum cryptography: Impossibility and constructions
 Journal
 SIAM Journal on Computing
 Volume  Issue number
 43  1
 Pages (fromto)
 150178
 Number of pages
 29
 Document type
 Article
 Faculty
 Interfacultary Research Institutes
 Institute
 Institute for Logic, Language and Computation (ILLC)
 Abstract

In this work, we study positionbased 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 positionverification 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 $\psi\rangle \in {\cal H}_A \otimes {\cal H}_B$. Their goal is to calculate and share a new state $\varphi\rangle = U\psi\rangle$, 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 $\varphi'\rangle$ that coincides with $\varphi\rangle = U\psi\rangle$ up to local operations on $A$ and on $B$, which are determined by classical information held by Alice and Bob. The oneround 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 positionverification scheme. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure positionverification is achievable. Jointly, these results suggest the interesting question whether secure positionverification 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 positionverification 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 positionverification is achievable, other positionbased cryptographic schemes are possible as well, such as secure positionbased authentication and positionbased key agreement.
 URL
 go to publisher's site
 Language
 English
 Note
 c? 2014 Society for Industrial and Applied Mathematics
 Permalink
 http://hdl.handle.net/11245/1.439675
 Downloads
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.