By Andreas Bluhm, Matthias Christandl, and Florian Speelman
Imagine that you are sitting in front of your computer and are about to enter your account information into your bank’s website because you need to transfer money to your sibling who lives abroad. Suddenly, you start to worry; does your bank really operate this website, or is some villain trying to trick you into revealing the PIN for your bank account? The website has the bank’s logo and looks like you would expect, but how can you be certain? After all, hackers can fake the appearance of a website.
Now suppose that you could somehow ensure that the server with which you are interacting is located in the basement of your bank’s local branch. Would that reassure you? Many people would likely answer “yes,” because it would be very difficult for a scammer to set up a manipulated computer at the bank without anyone noticing.
Figure 1. You and your friend (in blue) send the numbers “3” and “8” to the server at the bank (in green), which has to add them and tell you whether the sum is even or odd. Figure courtesy of the authors.
This example illustrates the idea behind position-based cryptography; instead of a secret key, the location of a party—in this case, the server with which you are communicating—becomes a credential to establish trust. What could a protocol to securely establish a server’s position look like? To facilitate things, visualize a situation wherein the house of a friend you trust is located the same distance from the bank as your house in a position that it is exactly opposite to yours — your house, the bank, and your friend’s house are all on a line. Your task is to ensure that the server in question is halfway between you and your friend. How could you do so? Perhaps you might create the following scheme: Both you and your friend send a number between 1 and 100 to the bank, such that both numbers arrive at exactly the same time. The server must then add the numbers and let both of you know whether the sum is even or odd (see Figure 1). Assuming that you and your friend know the numbers that you sent, you could easily verify the answer’s accuracy.
If you send the numbers via radio waves, the signals are transmitted at the speed of light. So, if the bank is 3 kilometers (km) away from your house, your number arrives 10 microseconds (µs) after it was sent. Since no information can travel faster than the speed of light due to special relativity, you can be sure that the sender is not more than 3 km from either of you if you both receive the correct answer 20 µs after you sent the numbers. Thus, the sender must be at the location of the bank directly between your two houses. If the sender was closer to your friend’s house, your number would arrive at the sender’s location after your friend’s number. Since it is not possible to know whether the sum of the numbers is even or odd without your number, you would only receive the correct answer after more than 20 µs.
As we have just seen, our scheme is secure against a single attacker. But what about two collaborating attackers, whom we’ll call Alice and Bob? If Alice is located between you and the bank and Bob is between the bank and your friend’s house, Alice could intercept your number, write it on a piece of paper, and send it on to Bob. If Bob does the same thing with your friend’s number, then the attackers would know both numbers in a timely manner — such that Alice can send the correct answer to you and Bob can send the correct answer to your friend (see Figure 2). From your perspective, there would be no difference between the replies of a server at the bank and the replies of two attackers somewhere outside the bank building. Any position verification scheme that relies solely on ordinary computers can thus be perfectly broken [5].
Figure 2. The attackers (in red) store the numbers that they intercept and send a copy to their partners. Having each received the number that they did not know from the other attacker, they then add both numbers and output the sum as even or odd. Figure courtesy of the authors.
This is where quantum mechanics comes into play. While a bit can assume the values 0 or 1, quantum bits—called qubits—can take values (or states) that are described by two-dimensional unit vectors with complex entries. A fundamental result of quantum information theory is that a qubit in an unknown state cannot be copied; this notion is called the
no-cloning theorem [7]. In our description of Alice and Bob’s attack on the position-verification protocol, they can copy the intercepted numbers before passing them on. The idea of
quantum position verification is to ensure that such attacks are impossible when sending qubits instead of bits. Alas, this picture is a bit too simple; if you can employ the power of quantum mechanics, Alice and Bob can do so as well, which makes them more powerful. In particular, they can use pairs of qubits that are entangled, which exhibit properties that pairs of bits do not. By measuring their respective quantum particles in the right way, Alice and Bob can obtain bits that look perfectly random to them, but for which they can be sure that if Alice obtains value \(b \in\{0,1\}\), then Bob also obtains \(b\) (and vice versa). In particular, Alice and Bob can use these entangled pairs to teleport quantum states: making Alice’s unknown quantum state appear on Bob’s side by sending only bits, and destroying Alice’s quantum state in the process. By utilizing quantum teleportation in an ingenious way, Alice and Bob can also break any quantum protocols for position verification — at the cost of expending many entangled pairs [1, 3].
Is all hope for secure position verification lost? No, because it is very difficult to store entangled pairs without destroying their quantum properties; this feature makes the construction of quantum computers very challenging. If we could find a protocol that would necessitate more entangled qubits than even the most advanced laboratories in the world can control in order to break it, that protocol would still be practically secure.
Our recent work—which is based on the so-called qubit routing protocol by Adrian Kent, William Munro, and Timothy Spiller [6]—did exactly that [2].
Compared to the protocol with two numbers that we initially described, the only change is that you now send both a number and a qubit to the bank while your friend continues to send just a number. The server adds the two numbers as before. But instead of simply answering whether the sum is even or odd, it returns the qubit to you if the sum is even and sends it to your friend if the sum is odd (see Figure 3). But how can you make sure that the qubit you ultimately receive is actually the one you initially sent? One possibility would be to prepare an entangled pair at the beginning of the protocol and send only one of the two qubits to the bank, opting to keep the other in a safe place. At the end of the protocol, you measure both qubits—the one you received and the one you kept—and check if they agree. If someone sent you a different qubit, then the two qubits at the end would no longer be entangled.
Figure 3. You and your friend (in blue) send the numbers “3” and “8” to the server at the bank (in green), and you send a qubit as well. The server adds the numbers and must return the qubit to you if the sum is even and to your friend if the sum is odd. Figure courtesy of the authors.
More formally, we proved the following statement: If the numbers that you and your friend send during the protocol are described by random strings \(x\) and \(y\) of \(n\) bits each, a Boolean function \(f\) exists on these bit strings (not necessarily the parity of the sum of \(x\) and \(y\), but potentially something more complicated) such that if \(f(x,y)\) determines whether the qubit should be sent to you or to your friend, any attackers that each control at most roughly \(n/2\) qubits will be detected with a small probability. We can bring this probability arbitrarily close to 1 by repeating the protocol several times. Moreover, the protocol can be made robust to a small amount of noise, and a variant of it is still secure if the qubit travels slower than the speed of light — both of which are required for possible implementations via fiber optics. The proof—which builds upon a previous approach [4]—establishes that Alice and Bob must decide on a strategy before they can communicate, which limits their number of possible tactics. Compared to this number, the number of Boolean functions on \(2n\) bits (which is \(2^{2^{2n}}\)) is huge if the number of qubits that Alice and Bob control is limited. Therefore, a function must exist for which all strategies of the attackers fail.
To summarize, the honest parties in the routing protocol only have to manipulate a single qubit when sending bit strings of length \(n\); any attackers need \(n/2\) qubits to escape detection. In other words, you can spend normal bits to increase the number of qubits that the attackers require to avoid detection. If the best laboratories in the world could control 1,000 entangled pairs, you could simply send 2,000,000 bits and the attackers would in turn need about 1,000,000 entangled pairs to succeed — which is an impossible task! Because this routing protocol is within reach for current technological capabilities, implementations could use quantum information in the not too distant future to verify the location of the parties involved and increase the security of online banking and other applications that involve the exchange of sensitive data. While some challenges remain, our work represents an important step towards this goal.
References
[1] Beigi, S., & König, R. (2011). Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New J. Phys., 13(9), 093036.
[2] Bluhm, A., Christandl, M., & Speelman, F. (2022). A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Phys.
[3] Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., & Schaffner, C. (2014). Position-based quantum cryptography: Impossibility and constructions. SIAM J. Comput., 43(1), 150-178.
[4] Buhrman, H., Fehr, S., Schaffner, S., & Speelman, F. (2013). The garden-hose model. In Proceedings of the 4th conference on innovations in theoretical computer science (ITCS ’13) (pp. 145-158). Berkeley, CA: Association for Computing Machinery.
[5] Chandran, N., Goyal, V., Moriarty, R., & Ostrovsky, R. (2009). Position based cryptography. In Advances in cryptology - CRYPTO 2009 (pp. 391-407). New York, NY: Springer
[6] Kent, A., Munro, W.J., & Spiller, T.P. (2011). Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Phys. Rev. A, 84, 012326.
[7] Wootters, W.K., & Zurek, W.H. (1982). A single quantum cannot be cloned. Nature, 299(5886), 802-803.
Andreas Bluhm is a postdoctoral researcher at the Centre for the Mathematics of Quantum Theory (QMATH) at the University of Copenhagen in Denmark. He obtained his Ph.D. from the Technical University of Munich. His research focuses on quantum information theory and quantum spin systems. Matthias Christandl is a professor in the Department of Mathematical Sciences at the University of Copenhagen and leads the Quantum for Life Center. He has previously held faculty positions at the University of Munich and ETH Zurich, and received his Ph.D. from the University of Cambridge. His research is in quantum information theory and quantum computation. Christandl is member of the Royal Danish Academy of Sciences and Letters. Florian Speelman is an assistant professor at the University of Amsterdam and QuSoft, the research institute for quantum software. He performed his Ph.D. research at the Centrum Wiskunde & Informatica in Amsterdam under the supervision of Harry Buhrman, and was a postdoctoral researcher at QMATH in Copenhagen and CWI Amsterdam. He researches quantum cryptography, protocols on quantum networks, and near-term applications of quantum computers.