Position-based cryptography (joint colloquium with Department of Computer Science) - Harry Buhrman

On 20 July 1969, millions of people held their breath as they watched, live on television, Neil Armstrong set foot on the Moon. Yet Fox Television has reported that a staggering 20% of Americans have had doubts about the Apollo 11 mission. Could it have been a hoax staged by Hollywood studios here on Earth? Position based cryptography may offer a solution. This kind of cryptography uses the geographic position of a party as its sole credential. Normally digital keys or biometric features are used. A central building block in position-based cryptography is that of position-verification. The goal is to prove to a set of verifier that one is at a certain geographical location. Protocols typically assume that messages can not travel faster than the speed of light. By responding to a verifier in a timely manner one can guarantee that one is within a certain distance of that verifier. Quite recently it was shown that position-verification protocols only based on this relativistic principle can be broken by attackers who simulate being at a the claimed position while physically residing elsewhere in space. Because of the no-cloning property of quantum information (qubits) it was believed that with the use of quantum messages one could devise protocols that were resistant to such collaborative attacks. Several schemes were proposed that later turned out to be insecure. Finally it was shown that also in the quantum case no unconditionally secure scheme is possible. We will review the field of position-based quantum cryptography and highlight some of the research currently going on in order to develop, using reasonable assumptions on the capabilities of the attackers, protocols that are secure in practice.