# 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 1There 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.

** Quantum Protocols **

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.

** Attacks **

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.

** A Theorem **

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.

** Open Problems **

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?

The “flaming arrow” of quantum cryptography (and quantum computing in general) is related to the physics question “Is quantum mechanics linear?”. It is immensely fun to trace-back the literature relating to this question, which is well-summarized by a 1989 article in

Nature, by Richard Thompson, titled (what else?)Is quantum mechanics linear?The evidence turns out to be precisely as strong, and thus precisely as weak, as the arguments in initial draft of Deolalikar’s claimed proof that

P≠NP. That is, the arguments presented are plausible on physical grounds, but weak on mathematical grounds.The counter-case, namely, the “flaming arrow” that quantum mechanics is

notlinear, is well-summarized in a 1997 article by Abhay Ashtekar and Troy Schilling (arXiv:gr-qc/9706069) titledGeometrical formulation of quantum mechanics, which concludes “the linear structure which is at the forefront in text-book treatments of quantum mechanics is, primarily, only a technical convenience and the essential ingredients—the manifold of states, the symplectic structure and the Riemannian metric—do not share this linearity.”The linear/nonlinear tension remains unresolved to the present day, and perhaps a fair summary is that folks who prove theorems tend to prefer the older Dirac framework of strictly linear quantum mechanics, whereas folks who work with classical dynamical systems and/or with hybrid classical/quantum dynamical systems find the modern symplectic frameworks to be more congenial. As for which framework

Natureherself prefers, no-one knows.We recommend to our engineering students the agnostic point-of-view is that it is best for young people to learn both kinds of quantum frameworks: linear and symplectic. The (shorter) linear path acquaints students with “quantum mysteries” as rapidly as feasible, the (longer) symplectic path begins to unravel the geometric and category-theoretic aspects of these mysteries, and both paths are well-worth traveling.

Is anything really secure? Access and time seem to be the only factors, and both are limited. At some point, if anyone gains access to your data, it is only a matter of time before they can understand it. Access is easier, but technology keeps making huge improvements on the time issues …

Yes, a one-time pad is currently the only known provably secure method of encryption – that is, one that is impossible to break (without the key). Encrypting a message with a one-time pad is secure because every possible decryption of the message is just as likely to be correct as any other. The disadvantage of one time pads of course is that the key must be at least as long as the message itself and that each pad may be used only once.

I am not an expert on this subject, but I would like to make a few comments on the history.

If you look at the original BB84 paper, Bennett and Brassard give their famous key distribution protocol and claim security, but they certainly do not prove security. It did turn out to be secure, but I believe the first proof was only given in 1992. Nowadays, there are much cleaner “device-independent” proofs that don’t have the device loopholes that are so frequently attacked. They are still subject to man-in-the-middle attacks if the channel is not authenticated. Authenticating a channel is another big problem.

As a bit of trivia, in the same paper, BB84 give a protocol for quantum coin tossing, for which they also give a heuristic security argument. This protocol turned out not to be secure.

It is possible to give quantum protocols that do not rely on the honest participants having any quantum devices. The EPR paradox is an example, where the verifier is fully classical. I think this makes finding loopholes much harder. The conclusion is still that if a soundness condition is violated, then either quantum mechanics or special relativity is false.

“The conclusion is still that if a soundness condition is violated, then either quantum mechanics or special relativity is false.”

If SR is false then Quantum Mechanics is false by definition. You can’t have the second without the first. If QM is false it might be possible to save SR but I doubt it.

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.In What to Do When the Trisector Comes, Underwood Dudley tells a story of a conversation with a trisector. He tells the trisector (truthfully) that the man has not proved angles can be trisected, but has shown their trisections can be closely approximated with his method. The would-be trisector was very happy with this, and Dudley concluded (from that story and others) that trisectors in general are just looking for some level of respect from the mathematical community and others. I think of this sometimes when I see how people respond to today’s claims of “complexity class trisection.”

The link looks broken…

Sorry. It worked for me. this hopefully links directly to the article. I don’t think there’s a paywall.

http://projecteuclid.org/euclid.cmp/1103940738

Apologies to Prof Dick Lipton for “spamming” with bad links. I went back and searched in a different way, and this should work. The links above don’t.

http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf

Let me rephrase… the link goes somewhere but that is to a 2-pg advertisement for the article, as far as I can tell.

Apologies about the link problem. I went at it another way this time. This should do it.

http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf

Without the need to give it much thought, quantum mechanics isn’t compatible with relativity therefore is it not bound to be “wrong”

somewhere?.Not assuming that this will allow to break any quantum protocol but who knows…

(Just like P=NP 😉 )

Quantum mechanics is compatible with special relativity, but not general relativity. So quantum protocols should be secure far away from black holes. 🙂 This is a guess, but I think quantum mechanics will likely survive in an eventual theory of quantum gravity, because quantum mechanics today is so much better understood and tested than gravity.

Hmmmm … a pretty good response to Dick’s question “Can we prove that quantum protocols are really secure?” can be constructed by quoting from two essays. The first essay is Don Knuth’s

Forward</i< to the book by Petkovsek, Wilf, and Zeilberger titledA = B… this is the essay that begins with the famous maxim: “Science is what we understand well enough to explain to a computer. Art is everything else we do.”The second essay is an article by Neal Koblitz and Alfred Menezes, titled

Another Look at “Provable Security”(2004), in particular the (short) concluding section titled“An Art or a Science? “To borrow a trope from Lemony Snicket, at this stage everyone should stop reading this post, and instead read these two essays (about four pages in total). Because both essays are absolutely outstanding.

Having read the essays, it will be clear that the short answer to Dick’s question is “No” and the longer answer is “No … but we can do much to increase our own confidence, and the public’s confidence, in cryptographic methods (both classical and quantum), via the kind of math, science, and engineering that broadly benefits the entire STEM enterprise.”

Absent from both essays is explicit mention of the word “quantum,” but there are passages in the Koblitz-Menezes essay that lead up to it as follows:

—————–

There are two unfortunate connotations of “proof ” that come from mathematics and make the word inappropriate in discussions of the security of cryptographic systems. The ﬁrst is the notion of 100% certainty. Most people not working in a given specialty regard a “theorem” that is “proved” as something that they should accept without question.

The second connotation is of an intricate, highly technical sequence of steps. From a psychological and sociological point of view, a “proof of a theorem” is an intimidating notion: it is something that no one outside an elite of narrow specialists is likely to understand in detail or raise doubts about. That is, a “proof” is something that a non-specialist does not expect to really have to read and think about. … Regrettably, many “provable security” papers seem to have been written to meet the goal of semantic security against comprehension by anyone outside the ﬁeld.

… Theoreticians who study the security of cryptographic systems should not try to emulate the practices of the most arcane branches of math and science. …

…

Chemists who investigate paramagnetic spin-orbit interactions do not seem bothered that their work is inaccessible to everyone outside a tiny circle of fellow specialists.This is to be expected, since their results and methods are intrinsically highly technical and out of reach to anyone who is not totally immersed in the narrow subﬁeld. Moreover, only a negligible proportion of the world’s people — somewhere between 2^{-25} and 2^{-30} — have any interest in what they’re doing; the rest of us do not care one iota about any of it.Cryptography is different. A lot of people in industry, government, and academia would like to truly understand to what extent they can have confidence in the systems used to protect, encrypt, and authenticate data.

—————–

In the above quotation, the passage about (quantum) “spin-orbit” interactions is emphasized because …. it’s the sole statement that the Koblitz-Menezes essay gets completely wrong (IMHO). That’s because issues connected with linearity, symplecticity, and simulability in quantum mechanics are coming to have simular public interest as cryptographic issues … for the very good reason that global-scale enterprises are coming to depend upon confidence in their accuracy.

Moreover, it is perfectly feasible to employ large-scale quantum spin simulations in the public exchange of cryptographic keys (our UW QSE Group has done this for fun); in essence Alice and Bob evolve publicly evolve a shared understanding of preferred bases as their cryptographic key.

That’s why, nowadays, it is mighty risky to assert that any aspect of the STEM enterprise is isolated from any other aspect … and for this reason, perhaps we should all of us be striving harder to heed Koblitz-Menezes’ closing assertion that “researchers should strip away unnecessary formalism, jargon, and mathematical terminology from their arguments and strive to make their work ‘look easy.'”

The attack by Lydersen et al. was clever, and important in that it demonstrated an attack on a commercial system that was claiming to be impregnable. But let’s not oversell their result or throw up our hands in despair.

It should be obvious by now that NO scheme can ever be completely secure in the real world. (Quick quiz: come up with 6 plausible ways to attack the one-time pad in the real world. See below for one answer.) All we can ever hope to do is to prove security within some model, which can equivalently be viewed as ruling out a certain *class* of attacks; that leaves us with the job of preventing other attacks, but at least it has made the adversary’s job harder.

How to attack the one-time pad? The bits of the key are probably not truly random; the attacker can try to trick the parties into using the same key twice; the attacker can flip bits of the ciphertext and observe the reaction of the receiver (i.e., a chosen-ciphertext attack); the attacker can hack into the computer on which the key is stored; the attacker can physically coerce the sender into giving him the message; the attacker can try to intercept the E&M radiation from the monitor displaying the plaintext.

That last method is unlikely – because LCD monitors emit no radiation. And tampering with an encoded message can be detected by encoding a message digest along with the text.

And whatever the practical shortcomings of a one-time pad may be, it is nevertheless the only method which provides “perfect secrecy” – meaning that the ciphertext provides no information about the contents of the message – even against an adversary with unlimited computing power.

Furthermore, if practical matters were all that important then there would be no reason to discuss quantum computing at all. For whatever the practical considerations of one-time pads may be – they are nothing compared to the practicality of building a quantum computer to encrypt a message.

A general remark::

Where do the random bits come from? This is not as easy as you might think.

LCD’s are vulnerable to EMI interception too.

http://www.omninerd.com/articles/TEMPEST_Attack_on_LCD

It’s true that generating random numbers is difficult. In fact, one reason the Soviets reused some of their one-time pads was probably due to the fact that the number of messages to encode exceeded the number of random numbers they could generate.

These days, I would probably go to Random.org which will generate random numbers for you from atmospheric noise.

My point was only that every system can be attacked. Schemes with mathematical proofs (whether quantum, or unconditional, or based on crypto assumptions) can be attacked if the model doesn’t match reality (e.g., the random bits used for the key are not really random) or by an attacker who goes outside the mathematical model used (e.g., a computer virus on the sender’s machine).

In the light of these developments, Is it beneficial to use some classic tools like formal verification and model checking techniques on quantum cryptography protocols? Has anyone already worked on this line?

Since no-one knows whether Nature’s quantum dynamics is

reallylinear, perhaps we can conceive of cryptographic protocols that work by exactly simulating linear quantum mechanics. That way, we are guaranteed to access all the mathematical beauty of linear quantum mechanics.To accomplish this, let |ψ⟩ be a public (simulated) quantum state, that is, a list of 2^

ncomplex amplitudes. Alice associates to this public state a set of 2^n randomly-chosen basis vectors, which she associates to the product states ofnnoninteracting spins, these random product-state basis vectors are Alice’s secret key. In effect, Alice’s secret key is a large, random unitary matrix … and to anticipate, she never shares this secret with anybody.Bob does the same, choosing a different (random) set of produce-state basis vectors, and thus Bob has different secret key, uncorrelated with Alice’s key, which he too never shares with anyone.

Then Alice and Bob simultaneously act upon the public state with weak, continuous Lindblad measurement processes. Everyone can watch the public state evolve … but only Alice and Bob know bases in which the public state is evolving toward a compressible representation as a finite-rank product state.

Alice doesn’t know Bob’s basis states, but she

cancompute a differential state-space vector from the public state to her nearest product state. Bob can do the same with respect to his product states. For geometric reasons, Alice’s state-space vector is anti-correlated with Bob’s; these anti-correlated differential vectors comprise Alice’s and Bob’s shared information stream. Furthermore, Alice and Bob needn’t view put all 2^n amplitudes on public view; it turns out that sparse random projections suffice.In effect, Alice’s dynamics are noise to Bob, Bob’s dynamics are noise to Alice, and the dynamics that Alice and Bob publicly expose looks like noise to everyone else.

It is easy and fun to verify that the preceding schema works in practice—as our QSE Group learned by trying it—such that any large-scale (open) quantum simulation alternatively and naturally functions as an algorithm for public key exchange. Because Alice and Bob exchange only (robust) numbers, rather than (fragile) quantum states, a great many practical implementation issues are finessed. In particular, the physical range of the method is unbounded, zero-noise amplification is feasible, and relay stations do not compromise security.

How secure is this general class of hybrid classical/quantum key exchange algorithms? Well … either it is easy to deduce Nature’s preferred quantum basis vectors, and thus solve the central hard problem of experimental quantum physics … or else it is hard to crack the above public quantum key exchange algorithm … and both possibilities are very interesting.

The intent of the above is

notto propose (yet another) public key exchange algorithm—there are plenty of those around—but rather to illustrate that the challenges and opportunities that are naturally associated to quantum cryptography and simulation are both immensely deepandimmensely wide. And both the depth and the width are fun! 🙂If one considers a “proof” only on the mathematical sense, than I would believe that the answer to the open problem is no. However, if one allows for some physical impositions than it might be possible. For example, Acin+Gisin+Masanes, PRL 97, 120405, proposed a quantum key distribution protocol which security relies solely on the non-existence of signaling, ie., no spooky action at distance. This shift of paradigm that quantum information brought with it is very deep. Actually, I would find very nice if questions such as P=?NP could be related to physical principles, like: if P=NP, then there must exist signaling. I know that must of you won’t be happy with that, thought.

As authors of a preprint that appeared simultaneously to the paper mentioned in the blog-post by Hoi-Kwan Lau and Hoi-Kwong Lo, we would like to quickly clarify

the historical context:

Adrian Kent has first been thinking about position-based cryptography in 2002 and together with co-workers from HP Labs, they have obtained a US-patent on an (insecure) scheme in 2006. They also discovered the same attack as Lau/Lo on some particular schemes in 2003, but their results did not appear in the academic literature until August 2010. These attacks only apply to schemes of a very specific form.

In our recent paper, we describe a generic attack that breaks any position-verification scheme. This includes all previously proposed schemes, in particular a scheme conjectured secure by Lau/Lo in their paper.

Thus, for position-based quantum crypto, we show that very general quantum impossibility proofs are possible, but they do not prevent us from studying (very realistic) restricted models where the adversary does not have the necessary resources to perform the attack. For the case of position-based schemes, it might be sufficient to restrict the amount of entanglement available to the adversary.

The recent ‘blinding’ attack highlights a disadvantage of QKD, which is that it can be difficult to get the hardware implementation to match the theoretical description of the protocol. Michael Nielsen wrote a nice explanation of this point several years ago.

An earlier commenter suggested that we’d need to build a quantum computer to implement QKD. In fact, this isn’t strictly true, but by the Nielsen arguments, it would certainly improve our belief in its security.

Also, I wouldn’t recommend basing your one time pad on bits from random.org (or any other website).

To clarify one thing, you can implement QKD w/o building a quantum computer because all you need in principle are single-photon sources and detectors, which are much easier to build than the minimal known components of a universal quantum computer. The challenge is that in practice you also need to make sure that there aren’t any side channels, and having your incoming and outgoing photons go through a quantum computer would definitely make this easier. Whether you consider this overkill depends on how paranoid you are.

A related question still in ordinary cryptography. One variant of the theorem that ends the post is that for every cryptosystem which looks immune (or even provably immune) there is a variant which looks as immune but really is breakable. (There is also a variant of Marphy’s law that such a cryptosystem will also be chozen for the next generation of cellphones.) Is there a formal study of this phenomenon. Of course, there is practical interest in constructing codes which look secure but in fact they are not, or even constructing codes which are usually secure but with some extra information, or for some special parameters, are not. But I am not aware of formal study of cryptosystems that look good and behave bad, how to define and construct them.

Gil, here is a not-too-serious (or is it?) answer to your question: “Another name for ‘a cryptosystem that looks good and behaves bad’ is ‘a mathematical magic trick‘.”

And indeed, didn’t the Allies call their WWII decryption capability by the name of “MAGIC”?

Gil,

What a wonderful idea. I love this idea. The only thing I even think that is slightly in this direction is one may be able have a program that generates bad public keys. But your idea is much more interesting.

You may want to take a look at work on “Kleptography” by Adam Young and Moti Yung.

One work I am aware of in this direction is here

http://libeccio.dia.unisa.it/Papers/Trapdoor/

A man-in-the-middle attack is always possible if Bob and Alice don’t know each other in advance.

This actually happened several years ago, during the rescue of Íngrid Betancourt. The two rebel-group generals who were arranging her secret movement from place to place had never met each other, and so did not know each other’s voices. For months, each of them talked separately on the phone with Mr. X, instead of with each other, as they believed.

Mr. X was part of the rescue team. He alternately pretended to be each of the generals when talking to the other on the phone. During the preparation period, he just passed along information from one general to the other one.

After a long period of gaining trust from the two generals, Mr. X arranged with one of them for Betancourt to be handed off to people they believed to be part of their group, but who were actually rescuers.

The deep problem is not data security, it is identity security.