Are Quantum Impossibility Proofs Possible?
Can quantum protocols be proved secure?
Charles Bennett is famous for his seminal work on reversible computation, quantum computation and protocols, and many other wonderful results. He also enjoys wordplay, here is one example:
The point is you can read the cycle starting anywhere and still get a meaningful phrase. Check his web site for an even more elaborate one.
Today I want to talk again about impossibility proofs. Recently, quantum protocols have been attacked, after they have been proved secure. Are impossible results really possible?
I have stated before that one of my all time favorite Far-Side cartoons is the one with “burning arrow,” and the question:
Can they do that?
I actually tried, by the way, to see if I could legally post that cartoon here—I was willing to pay a reasonable amount for the privilege—instead of the above. I went to the Far-Side official site, filled out a request form, and got back an email. No way. Gary Larson will never approve anyone to legally post his material on the web. Period. So no cartoon. Oh well.
It is possible to prove that something is impossible, but it sure is hard. My suggestion when anyone tries to tell you that X is impossible, is to translate it into the statement: It is not possible to do X with the following allowed methods Those methods may include all possible ones or they may not. That is the key issue: do the methods cover all possible ones, including burning arrows?
A classic example of an impossibility result is based on a famous problem first raised by the Greeks: angle trisection with only a ruler and a compass. I have discussed it before, but perhaps it is worth mentioning again—it is in the same post that talks about Larson’s cartoon. Pierre Wantzel proved in 1837:
Theorem 1 There is no general method for angle trisection that uses only
- An unmarked ruler;
- A compass.
Note, the proof of this famous theorem is perfect, but it can be “attacked.” With the allowed tools, certain angles can be trisected; any angle can be trisected up to an arbitrarily small error. Using slightly different tools, for example, a ruler with two marks, any angle can be trisected. So is angle trisection really impossible? Yes it is in a narrow sense, but beware of the burning arrows.
Bennett and Gilles Brassard first suggested quantum protocols for secret key exchange that might be impossible to attack, in a beautiful paper. The title is Quantum cryptography: public key distribution and coin tossing. —but the paper and its protocol are usually called just BB84.
Modern cryptography is really based on one of the most important notions of complexity theory: the notion of a reduction. A usual theorem in cryptography is of the form:
Theorem: If there is a method to break the protocol X in polynomial time, then there is an algorithm that solves Y in polynomial time.
The brilliant idea of BB84 was to change this to theorems of the form:
Theorem: If there is a method to break the quantum protocol X, then quantum mechanics is wrong.
Note, two differences. There is no restriction on the resources used by the adversary to break the quantum protocol, and second the consequence of an attack on such a protocol would be terrible: the consequence would be that quantum mechanics is wrong. Any theory, including quantum mechanics, may eventually need to be modified or extended. But for quantum theory to be wrong would be an immense result. The theory is “tested” every day when we use modern devices, the theory continues to pass all the strange predictions that it makes, and it would be very surprising to find it wrong.
This is the beauty, the promise, and the excitement of quantum protocols. They have changed how protocols are proved secure. Classic security protocols are usually based on the hardness of a computational problem such as:
- The factorization of numbers that are the product of two large random primes.
- The solving of discrete logarithms over large finite fields.
- The solving of other number theoretic problems.
- And more recently certain lattice based problems.
What makes—made—quantum protocols so different was that the hardness was based on the correctness of quantum mechanics. The hope was that anyone who broke a quantum protocol would have to show that quantum mechanics is wrong. We believe in quantum mechanics, since its predictions have been spot on, so this seems like a pretty neat idea. This is why BB84 was such a major result, and why it generated so much interesting subsequent research.
The trouble is there are quantum attacks that use quantum burning arrows.
There is now a long history of quantum protocols, with a corresponding large literature. The promise is still there, but quantum protocols have been just as fragile to the exact assumptions as classic protocols. Quantum proofs of impossibility of attacks have often failed—just as it has happened over and over in classic hardness based cryptography.
Here is a quote from a paper by Dominic Mayers in 1997:
In 1993, a protocol was proposed to realize bit commitment in the framework of quantum mechanics, and the unconditional security (see sections b and c) of this protocol has been generally accepted for quite some time. However, this result turned out to be wrong.
Here is another quote from a 2010 paper by Hoi-Kwan Lau and Hoi-Kwong Lo:
Recently, position-based quantum cryptography has been claimed to be unconditionally secure. In contrary, here we show that the existing proposals for position-based quantum cryptography are, in fact, insecure
A recent paper got my attention, since it showed how to break quantum based protocols by a general “man-in-the-middle” attack. A popular description of the paper is here, and the technical version is here. The result is due to Lars Lydersen, Carlos Wiechers, Christoffer Wittmann, Dominique Elser, Johannes Skaar and Vadim Makarov. They point out in their paper that their attack is against implementations, not against the fundamental idea of quantum protocols. Here is a figure from the paper outlining the attack. The left end connects to Alice and the right end to Bob.
Roughly, Eve, the eavesdropper, does the following:
- She receives photons from the real Alice, pretending to be Bob.
- Eve proceses them as Bob would, and then sends then off to the real Bob.
When the protocol is done, the secret is shared by all three—Alice, Bob, and Eve.
I will not try to give an even partial survey of all the results and counter-results in the last few decades. The key point to take away is simple: quantum protocols have many interesting advantages over classic ones, but they can be attacked.
One must be very careful to check what the attacks are and whether those attacks cover all feasible ones.
What is interesting about breaks in classic systems and breaks in quantum systems is that they usually, if not always, are fixable. The attack exploits some gap in the impossibility proof and the gap often can be fixed by modifying the protocol—sometimes very slightly. This is summarized in what I will call the Crypto Designer’s Theorem:
Theorem: For every crypto-system that is broken by some attack, there is another system with the following properties:
- The attack fails for .
- The system is a small modification of .
I leave the proof of this theorem to the reader.
Can we prove that quantum protocols are really secure? Or are we always going to have to worry—like classic systems—that someone will discover a burning arrow? What do you think?