Proving You Are Where You Say You Are

SINGAPORE—When a speaker brings a tangle of garden hoses, a bottle of water, and a towel to the podium, you know it’s going to be a fun talk. Computer scientist Harry Buhrman of the Centrum Wiksunde & Informatica in Amsterdam recently visited Singapore to help celebrate the fourth anniversary of the Centre for Quantum Technologies. He and his props gave quantum cryptography a whole new dimension—literally. Instead of encrypting a message or authenticating someone’s identity, Buhrman posed a deceptively simple question: Can someone be sure you are where you say you are?

Position verification isn’t just of interest to spouses who wonder about all those late nights at the office. It would tighten up secure communications channels and make it possible to send Mission Impossible-style messages that could be read only if someone visited a certain location (like geocaching puzzles). For fundamental physicists, the procedure raises an important question about the operational meaning of space. If you cannot confirm, even in principle, whether something is at a given location, does the concept of location have any objective meaning? In fact, the scenario Buhrman laid out bore a spooky resemblance to the holographic principle in quantum gravity.

Figure 1

Imagine trying to confirm your position in one dimension, along a straight line (Figure 1). A verifier can use the procedure of Einstein synchronization: send you a signal, to which you reply, and measure the round-trip time in order to gauge the distance between the two of you. It is the maximum distance; you might be closer, given the delays that could arise in the process. To narrow down your location, a second verifier on the opposite side of you also sends a signal that you must reply to. This technique goes by the name of distance bounding.

Figure 2

It’s easy to game the system, however (Figure 2). Two comrades intercept the signals, wait a short while (to simulate the travel time to your purported position), and reply on your behalf. Now you don’t need to be where you claim to be. With your friends covering for you, you can safely leave the office and have your affair.

Figure 3

Having been cheated once, the two verifiers, to try to foil you, might ask you to perform a task that requires information from both of them (Figure 3). For instance, they each send you a number and demand that you calculate the sum, on the principle that you need to be where you say you are in order to receive the two numbers and add them up.

Figure 4

But this system, too, is fool-prone (Figure 4). Each of your comrades can intercept the signal, make a copy, and relay it to the other. That way, both can perform the calculation and send back the result just as if you were really there.

Figure 5

Because this fakery requires your comrades to copy the information, the verifiers figure they can ensnare you by exploiting ideas from quantum cryptography--namely, that a quantum state cannot be reliably copied (Figure 5). The verifier on the left sends you a photon in a certain quantum state and the one on the right sends you a single ordinary bit. To confirm your position, you need to return the photon to the left if the bit is 0 and send it on the right if the bit is 1. Unable to make a copy of the photon, your comrades are at a loss for how to cover for you.

Figure 6

But being good quantum physicists, not to mention good friends, they soon realize a trick. In advance, they prepare entangled pairs of particles (Figure 6 and Figure 7). These pairs can transmit the quantum state–and therefore, in effect, the photon itself—between them using the process known as quantum teleportation. This allows them to set up a game of photon hot potato. The friend on the left side of your purported position intercepts the photon and teleports it to your friend on the right. If the bit is 1, the friend keeps it and sends it to the right verifier; if it is 0, the friend on the right teleports the photon back to the left.

Figure 7

Last year Buhrman and his colleagues proved that in general, no quantum cryptographic scheme is guaranteed to expose a location cheater (see this paper) and recently they laid out a general recipe for evasion. That’s where the hoses come in (see this paper). Teleporting a particle is like pouring water in a hose—it comes out the other side. Each of your friends connect the hoses in a certain way so that the photon flows back and forth and ends up on the side where it’s supposed to be. Buhrman demonstrated this on stage with hoses he’d bought at a garden supply store. We were all grateful he’d brought a towel.

The whole thing sounded very reminiscent of the holographic principle. (For more on the holographic principle, see this Scientific American article, “The Illusion of Gravity.”) One of the deepest principles in quantum gravity, it holds that the amount of information within a region of space does not scale with the volume but with the area. It is always possible to simulate the goings-on within a region of space perfectly by manipulating its boundary. You really can read a book by its cover.

That is precisely what is happening in position evasion. Your two comrades are the boundary in one dimension, and they can connive to pretend that you’re in between them when you’re not. “By being on the surface, you can simulate any behavior on the inside,” Buhrman told me. So there is a very general reason why cheaters can always succeed. And this is in a system with no gravity.

It is mildly disturbing that it is always possible to fake a position. The verifiers do have the last laugh, though. They can place such exorbitant demands on your friendship, requiring them to share an impractically large number of entangled pairs of particles and execute elaborate schemes for tossing the photon back and forth between them, that even your BFF would probably sell you out.

Images adapted from slides by Harry Buhrman. This post first appeared on the Foundational Questions Institute blog.