What is position-based cryptography?

The goal of position-based cryptography is to use the geographical location of a player as its (only) credential. For example, one wants to send a message to a player at a specified position with the guarantee that it can only be read if the receiving party is located at that particular position. In the basic task of position-verification, a player Alice wants to convince the (honest) verifiers that she is located at a particular point. A more advanced task is secure position-based authentication where it is guaranteed that a received message originated from a particular position and was not modified.

Practical examples of position-based cryptography include military or banking scenario or the pizza-delivery problem where one wants to make sure that pizzas can only be ordered from within a certain radius from the pizzeria.

Classically impossible

It has been shown by Chandran, Moriarty, Goyal, and Ostrovsky that position-verification using classical protocols is impossible against colluding adversaries (who control all positions except of the prover's claimed position). They show that memory-restrictions on the adversaries are required to have secure schemes in this model.

History of position-based quantum cryptography (dates generally refer to first appearance as preprint)

2002: Under the name of quantum tagging, the first position-based quantum schemes are investigated by Kent. A US-patent was granted in 2006, but the results have only appeared in the scientific literature in August 2010.
March 2010: Malaney posts his independent work on Location-Dependent Communications using Quantum Entanglement and Quantum Location Verification in Noisy Channels on the arxiv. No rigorous proofs are provided.
May 2010: Chandran, Fehr, Gelles, Goyal, Ostrovsky propose a quantum scheme for position-based identification (and other tasks) with rigorous security proof, but implicitly assuming no pre-shared entanglement.
August 2010: Kent, Munro, Spiller show the insecurity of the previously proposed schemes if adversaries hold pre-shared entanglement. They also proposal new (secure?) schemes.
August 2010: Kent, Munro, Spiller show the insecurity of the previously proposed schemes if adversaries hold pre-shared entanglement. They also proposal new (secure?) schemes.
September 2010: Lau, Lo show an extension of Kent et al.'s attack to higher dimensions. They propose new (secure?) schemes. They give a security proof against 3-qubit entangled state.
September 2010: Buhrman, Chandran, Fehr, Gelles, Goyal, Ostrovsky, Schaffner show the general impossibility of position-based quantum cryptography in case the adversaries share huge number of EPR pairs (doubly-exponential in the number of qubits the honest player operates on).
January 2011: Beigi and König improve the amount of EPR pairs needed in the general attack against position-verification protocols to exponential. They also show that a particular protocol remains secure against adversaries who control only a linear amount of EPR pairs.
April 2011: Kent points out that QKD between the prover and the verifiers can be used for quantum position verification in case the prover holds some secret key which is unknown to the attackers.
September 2011: Buhrman, Fehr, Schaffner and Speelman examine a class of protocols that only require the communication of a single qubit and 2n bits of classical information. They define a new model of communication complexity, the garden-hose model, which enables 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 quantum position-based cryptography to traditional complexity theory.
November 2011: Gilles Brassard writes about position-based cryptography and our impossibility proof in the News & Views section of Nature.
April 2012: Arie Matsliah and Oded Marglit from IBM Research in Haifa use the IBM SAT-Solver to improve the garden-hose complexity of computing the equality function. A variant of the problem is posed as April's official "Ponder This" problem on the IBM website..
October 2012: Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski and Stephanie Wehner show a quantum-information theoretical result about the monogamy of entanglement, with an application to position-based cryptography.
Dec 2013: Chiu, Mario Szegedy, Wang and Xu are fascinated by the symmetries in the problem of determining the garden-hose complexity of the equality function. They are the current world-record holders with 1.359n. Can you do better?
Feb 2014: Dominique Unruh gives a quantum position-verification scheme in the random-oracle model and gives an efficient position-based authentication protocol.
Dec 2014: Hartmut Klauck and Supartha Podder give new bounds for the garden-hose model.
Feb 2015: Qi and Siopsis study position-based quantum crypto in a realistic setting where channels are lossy. This turns out to be quite a problem for security and requires new protocols to solve the issue.
May 2015: Jérémy Ribeiro and Frédéric Grosshans prove a tight lower bound for the single-qubit BB84 protocol, using results and techniques from the noisy-quantum-storage model.
July 2015: Kaushik Chakraborty and Anthony Leverrier show that various simple protocols can be attacked with a polynomial amount of entanglement. They suggest a new Interleaved Product protocol which is conjectured to resist known attacks.
November 2015: Florian Speelman shows how to use garden-hose magic in order to do instantaneous non-local computation of low T-depth quantum circuits. As an application, he gives an attack on the interleaved-product protocol which uses only polynomially many EPR pairs.
Sep 2018: Everything you ever wanted to know about port-based teleportation (and more) can be found in this compendium article by Christandl, Leditzky, Majenz, Smith, Speelman and Walter.
February 2019: A recent development in quantum gravity research has been understanding that recording a higher dimensional theory into a lower dimensional one (which we think must happen in quantum gravity) requires large amounts of entanglement in the low dimensional theory. Interestingly, this result can actually be viewed as a consequence of the position-based quantum crypto security proofs in the no entanglement setting! Alex May derives a more precise consequence along these lines in his paper.

Publication and presentations

Our impossibility proof is published in the proceedings of the IACR CRYPTO 2011 conference. The full article is available on the arxiv. Out of over 200 submissions, it has been selected as one of three plenary talks at QIP 2011, the biggest workshop in the area of Quantum Information Processing. You can find our 3-page abstract and the video and slides of Serge Fehr's presentation online.

We have given various other presentations about position-based quantum cryptography, for example at the workshop on post-quantum security models in Paris (France), Caltech (USA), the Canadian Institute for Advanced Research (CIFAR), the universities of Aarhus (Denmark), Cambridge (UK), Eindhoven (NL), Utrecht (NL), and Aachen (Germany).

We have given talks about the subject at various venues including at QCRYPT 2011, QIP 2012, The China Theory Week in Aarhus, Quantum Computer Science workshop in Montreal and several seminars.

News Articles

Last update: Dec 2015