(Aug 23rd, 2012) An overview of position-based quantum cryptography.

An overview of position-based quantum cryptography.


Introduction

Imagine a secure cryptographical protocol where you can use your geographical position as a credential. For example, you could register your home location at your bank to secure your on-line banking account from connections not originating from your home PC. Or, as a military organization, you could send an encoded message that only troops deployed at a certain location could read. In general, this would link the security of the digital world to that of the physical world - the Holy Grail of on-line security. This is exactly what position-based cryptography (PBC) tries to achieve, and its goal has proven to be all but trivial. In fact, in order for this model to be meaningful, the geographical position cannot be obtained by external measurement services, which would then become the weak link of the security chain. I.e., it would not make sense to rely on something like the GPS satellite system to obtain coordinates, since this would open a plethora of new attack scenarios. The position should instead depend on some intrinsic properties of the system involved, something as cheating-proof as possible. In practice, this means to exploit some physical law which we are guaranteed to be unmodifiable by any known attacker - just as the GPS system relies on the constant speed of light to pinpoint position.

Cryptosystems relying on the idea of exploiting the physical world are theoretically unbreakable as long as the physical law holds, as their security does not depend, in principle, on any computational assumption. They are, of course, prone to implementation issues like any other cryptosystem, but we are guaranteed that as long as we understood correctly the physics we must not fear any surprise.

Must we?

The gap between theory and practice has always proven to be unpredictably wide and, as often happens, the good and the bad guys can use the same tools. The same physical properties which allow to create strong cryptograms also allow to devise new powerful attacks. In this article we will give an overlook of the rise, evolution, fall and resurrection of position-based cryptography augmented with the magic of quantum physics, keeping in mind that there is no final word to the everlasting arms race of security.



Classical PBC

A formalized model for PBC was first introduced - and proven to be insecure - in [CGMO09]. The idea of the original protocol was to achieve secure position verification via a distance bounding protocol based on relativistic assumptions (namely, the speed of light) and involving multiple verifiers to authenticate an honest prover.

Let us see an example in the 1-dimensional case. Consider a segment of space [0,1] and two verifiers, V_0 and V_1, sitting at positions 0 and 1 respectively. Then we have an honest prover P, standing at position 0.6, whose goal is to convince the two verifiers that he is located exactly at that position. We assume the following:

• there is a fixed and publicly known Boolean function f:{0,1}^n X {0,1}^n -> {0,1} which is very easy to compute and takes virtually no time to be evaluated for reasonable values of n
• the two verifiers V_0 and V_1 share a private channel which they can use to securely communicate with each other and synchronize their clocks
• all the parties are able to communicate just at a fixed, bounded speed (i.e.: we assume that they can broadcast radio waves or laser pulses at the speed of light)

Under these assumptions we can design many different position verification protocols, here is an example:

1. P initializes the protocol, sending a request to the verifiers to be authenticated at position 0.6
2. V_0 generates a random n-bit string x and shares it with V_1 through the private channel, V_1 does the same with another random n-bit string y
3. V_0 generates a random bit b and, if f(x,y) = 1, sends a copy of b to V_1 through the private channel
4. V_0 sends x and b to P, and V_1 sends y to P; they time their messages so that x, y and b arrive all at the same time at position 0.6
5. P evaluates f(x,y): if the result is 0 then P routes back b to V_0, otherwise he routes b to V_1
6. the verifiers accept the round if and only if V_f(x,y) receives the correct b at a time which is consistent with the claimed position 0.6 given the speed of light of the signal
7. repeat the previous steps for k times (where k is a security parameter) for security amplification and authenticate P's position if and only if all the k rounds are passed.

It is pretty clear that a single malicious prover standing at a position different from what claimed cannot cheat with probability greater than 1/2 at each round. But it is easy for two colluding malicious provers, M0 and M_1 standing, e.g., at positions 0.3 and 0.8 respectively, to trick the verifiers into believing that there is a single honest prover at position 0.6, namely:

1. as soon as M_0 receives x and b from V_0, she forwards a copy of both to M_1; M_1 does the same by forwarding a copy of y to M_0
2. as soon as M_0 receives y from M_1, she computes f(x,y) and, if 0, sends b to V_0, otherwise does nothing; at the same time, as soon as M_1 receives b and x from M_0, she sends b to V_1 if f(x,y) = 1, otherwise does nothing.

It is easy to check that by summing up the travel time of the malicious attacker's messages, either V_0 or V_1 will receive the right b at the right time, hence the attackers can convince the verifiers that there is a honest prover at any given position between them.

This argument (formally proved in [CGMO09]) can be extended to any distance bounding protocol, concluding therefore that secure classical PBC against multiple adversaries is unachievable.



Quantum PBC

First ideas for quantum PBC (QPBC) appeared in the academic literature in 2010 [KMS10]. The idea is the following: since the above multi-adversary attack to classical PBC protocols relies on creating copies of some bit and keeping them before relying to the correct verifier, this attack fails if we use quantum bits (qubits) instead.

It is well known that a quantum state cannot be copied. In mechanical physics this is called the "No-Cloning Theorem", and it is a consequence of the thermodynamical Landau's Principle stating that in order to erase information embedded in a physical system one has to spend energy. Since in a closed physical system the total energy must be conserved, and since in order to copy a qubit one has first to "free space" (erase another qubit) to copy the given state into it, it turns out that it is impossible to copy a qubit in a reversible way. The other option is to have the system interact with another system (the observer) in order to measure the given qubit and then prepare another qubit from scratches in the measured state. But by the postulates of quantum mechanics, the process of measurement destroys the original quantum state with very high probability, it is therefore impossible to make a perfect copy of a qubit. This "magic" property of quantum mechanics has been exploited to design new, innovative, unconditionally secure cryptographical schemes and it is at the base of quantum cryptography [BB84].

In QPBC, part of the information exchanged by prover and verifiers consists of some quantum state |phi> which must be measured at a certain step of the protocol and act as a "guarantee" that the particular step can be only performed once for every round. Under the same conditions as the protocol in the previous section, let us consider the following quantum variation:

1. P initializes the protocol, sending a request to the verifiers to be authenticated at position 0.6
2. V_0 generates a random n-bit string x and shares it with V_1 through the private channel, V_1 does the same with another random n-bit string y
3. V_0 generates an entangled EPR pair |ab> = (|00>+|11>)/sqrt(2); if f(x,y) = 1, he sends the first half of the registry, |a>, to V_1 through the private channel, otherwise keeps this half for himself
4. V_0 sends x and the other half of the EPR registry, |b>, to P, and V_1 sends y to P; they time their messages so that x, y and |b> arrive all at the same time at position 0.6
5. P evaluates f(x,y): if the result is 0 then P routes back |b> to V_0, otherwise he routes |b> to V_1
6. the verifiers accept the round if and only if V_f(x,y) receives the qubit |b> at a time which is consistent with the claimed position 0.6 given the speed of light of the signal and it is consistent with a Bell measurement performed together with the other half |a>
7. repeat the previous steps for k times (where k is a security parameter) for security amplification and authenticate P's position if and only if all the k rounds are passed.

A Bell measurement over two qubits in this case is just a "test" to see whether the two qubits have preserved entanglement or not. Since measuring any of the two qubits destroys entanglement, if this test is passed it means that the qubit |b> has not been measured (and hence has not been replaced nor partially copied). Under this condition it is clear that no coalition of malicious attackers can impersonate a honest P with good probability. In fact, the attack to the classical protocol relies on the fact that the bit b can be copied and distributed amongst the attackers without the verifiers noticing it, which turns out to be impossible with the quantum state |b>. Notice that this protocol only needs a single EPR pair for each of the k round in order to achieve k bits of security, which is pretty efficient.



Breaking QPBC

QPBC looks really unbreakable so far, but unfortunately it does not keep into account the fact that entanglement can also be used by malicious attackers to perform one of the weirdest feats of quantum information: distributed computation via teleporting. This is a consequence of the fact that entanglement between qubits is a non-classical interaction, very different from anything we have been knowing in the last few centuries, like electromagnetic or gravitational interactions. One of its consequences is that if two parties share an entangled EPR pair, then one of the parties can teleport an additional qubit to the other party by sending two classical bits of information and destroying the EPR pair by performing a Bell measurement over the qubit and one of the halves of the EPR pair [NC00]. Let us now see how this can be used by malicious attackers M_0 and M_1 to break the QPBC protocol above in the case where n=1 and f(x,y) = x XOR y:

1. M_0 and M_1 share three entangled EPR pairs, labelled 0, 1 and 2 respectively, and initialize the protocol
2. let's assume that f(x,y) = 0, then M_0 receives x (a 1-bit string) and |b>, while M_1 receives the 1-bit string y
3. M_0 uses the EPR pair labelled x to teleport |b> to M_1, and sends x and the two classical bits for teleportation to M_1 (notice that these three classical bits will travel at the speed of light)
4. at the same time, M_1 teleports her half of the EPR pair labelled y using EPR channel 2, and sends y and her two classical teleportation bits to M_0 (again, these three bits will travel at the speed of light)
5. when the classical bits arrive at their destinations (in a single round of simultaneous communication), both cheaters can compute f(x,y)
6. if f(x,y) = 0, then it is easy to check that |b> has been teleported in M_0's EPR register 2 (and M_0 is able to recover it since she has also received M_1's teleportation bits); otherwise it is easy to check that |b> has been teleported in M_1's EPR register labelled x (and M_1 is able to recover it, since she has received both x and M_0's teleportation bits)
7. in both cases, it is easy to check that, with a single round of simultaneous communication, the "correct" cheater has received |b> just in time to route it to the "correct" prover, hence breaking the security of the protocol.

This attack can be generalized to any n and any suitable f, the basic idea being the following: if the two attackers share an arbitrary amount of EPR pairs, then they compute the function f "in parallel", like if they were using a single (quantum) computer made of a split (quantum) register physically separated in space.

This is an intrinsic property of quantum computing: non-classical correlations are not limited to the speed of light (in a sense which is still not completely understood). For example it could be possible to have a two-qubit quantum computer where one of the qubits resides on Earth ant the other one is located on Mars, and still it would work perfectly like if we had a single joint register. It is proven, however, that it is impossible to exploit this property to make "miracles" - e.g.: to violate Einstein's relativity principle. Namely, even if the two registers are quantum-jointed (and it is thus possible to perform operations on both simultaneously), it is impossible to access the information of a remote register without transmitting classical information. This is exactly what the classical teleportation bits are for, the interesting part being that the process of computation can be "parallelized" through the EPR channels and can then be performed by using a single round of classical communication - which is enough to break our QPBC protocol.



Future directions

QPBC is thus proven to be insecure in case of multiple colluding attackers sharing an arbitrary amount of EPR pairs. But we must consider that EPR pairs are a costly resource (they are currently, and there is no evidence that they shouldn't be in the future). This has led to an interesting observation.

Let us forget for a second about entangled-capable adversaries and let consider the role of the parameter n in the QPBC protocol above. It has basically no importance, in the sense that the security of the protocol does not depend on it - while depending on the parameter k instead. This means that, in theory, there is nothing wrong in setting n = 1 and using a very simple function f, like the XOR example above. But if we consider the entanglement attack, while the same observation remains true for honest prover and verifiers, n makes a difference for the malicious attackers instead. Namely, the larger n, the more and more EPR pairs M_0 and M_1 need to share in order to compute f.

The QPBC protocol above is then interesting for the following fact: while it only requires a single EPR pair to be used by honest parties for each round, it requires some larger amount of entangled resources to be used by malicious attackers, and this amount in general depends on n. This trade-off can be stated as: the more (cheap) classical computing resources are needed by honest parties, the more (costly) entangled resources are needed by the attackers, which is a pretty nice feature.

This is not an absolute statement though, because it also depends on the function f. Namely, there exist easy to compute functions f where the amount of EPR pairs needed to compute f is small (such as logarithmic in n, or even constant). In order to exploit the aforementioned trade-off in real scenarios we have hence to find some - easy to compute, i.e. in P - functions where the number of EPR pairs needed for its evaluation grows as fast as possible in n.

The Garden-Hose Game is a computational model introduced exactly for this purpose: to model the EPR-related complexity of a function. It basically consists of two players (with their respective inputs x and y) separated by some distance who want to compute a Boolean function f(x,y) in the following way: they have some fixed pipes running between them, plus they have pieces of garden-hose which they can use to connect the ends of the pipes at their location into a pattern dependant on their input only (no communication allowed). There are no T-shaped (or more complex) pieces of hose, just one-to-one connections, but not all the pipes need to be connected. One of the players then has a source of water (tap) which is connected to one of the loose ends of the pipes. The players can arrange their hose pieces in such a way that f(x,y) = 0 if the water eventually reaches one of player 0's ends, 1 else. It is easy to see that water will eventually exit from one side or another, and that this model is closely related to the teleportation technique used to break QPBC. The Garden-Hose complexity GH(f) of a function f:{0,1}^n X {0,1}^n -> {0,1} is then defined as the minimum number of pipes necessary for the two players to compute its output for any input in the above way.

Some computational-theoretic results are known about bounds on GH(f), namely:

• GH(f) <= 2^n + 1, for any Boolean function
• if f is in L (computable in logarithmic space on a deterministic Turing Machine), then GH(f) is at most polynomial in n
• if GH(f) is polynomial in n, then f is in L (up to local preprocessing)
• if there exists an f in P such that GH(f) is super-polynomial in n, then P != L (notice that L is a subset of P, but it is currently unknown if the equivalence hold)
• there exist functions f such that GH(f) is exponential in n, but it is unknown whether they are also in P or not.

So, if we could find a function f which is in P, but has an exponential GH(f), that one would be a perfectly good candidate for use in QPBC, making the above attack infeasible for reasonable values of n. But the existence of such a function would imply a major breakthrough in computational complexity. Up to now only functions with polynomial Garden-Hose complexity are known, but the road is open to new, exciting directions.



References

• [BB84] Bennet, Brassard: "Quantum cryptography: Public key distribution and coin tossing", Proceedings of IEEE International Conference on Computers, System and Signal Processing


• [BCF+11] Buhrman, Chandran, Fehr, Gelles, Goyal, Ostrovsky, Schaffner: "Position-based quantum cryptography: Impossibility and constructions", CRYPTO 2011


• [BFSS11] Buhrman, Fehr, Schaffner, Speelman: "The Garden-Hose Game", arXiv:1109.2563v2


• [CGMO09] Chandran, Goyal, Moriarty, Ostrovsky: "Position-based cryptography", CRYPTO 2009


• [KMS10] Kent, Munro, Spiller: "Quantum Tagging: authenticating location via quantum information and relativistic signalling constraints", arXiv/quant-ph:1008.2147


• [NC00] Nielsen, Chuang: "Quantum Computation and Quantum Information", Cambridge University Press, 2000.