Stop the Myth: QKD doesn't fix what Shor broke

[Update: See More on the Myth.]

There is a lot of confusion about the relationship between two of the most famous results in quantum information theory: Shor's algorithm for factoring large numbers on a quantum computer and quantum key distribution (QKD) (developed originally by Charles Bennett and Giles Brassard in 1984). Shor's algorithm, of course, has implications for public-key cryptography.

It's important to note that a) QKD does NOT solve what Shor's factoring algorithm broke, and b) key exchange/distribution is not the biggest security problem we have on the net (it might not even make the top ten). The primary use of public-key cryptosystems is distributed authentication. The primary use of QKD will be key generation/exchange. They serve very different roles in the Internet. A secure Internet communication consists of several distinct parts - authentication of the parties involved, generation of a secure session key, and then the data encryption itself.

Your Internet Explorer, Mozilla, or Firefox comes with Verisign's public key built in. This allows you to check that yes, indeed, Verisign signed the key that says it came from Amazon.com, and therefore you can believe that you are truly connected to Amazon. This is what we call authentication.

After this authentication step, you must create a shared, secret key to continue the communication. That key exchange is often done via Diffie-Hellman key exchange, which allows parts of the communication to be done in the open (unencrypted). D-H by itself is vulnerable to a man-in-the-middle attack, so it is used with some form of authentication to create a shared, authenticated secret key for your session.

The difficulty of cracking a Diffie-Hellman exchange is, I believe, founded on the difficulty of the discrete logarithm problem, and hence is vulnerable to Shor. HOWEVER, D-H is not the only classical method of doing key exchange. If you already have a shared secret, it is easy to negotiate a key without D-H. I used to work for a startup that did IPSEC gateways (though I am FAR FAR from an expert on this), and I believe most of our customers did their authentication via pre-shared secret key. Though the IKE (Internet Key Exchange) built on that secret key authentication does use D-H, that can be fixed (by modifying the RFCs); when you have a pre-shared secret, you can easily use it to encrypt a new key chosen by one of the parties.

So Shor breaks public-key (PK) crypto. What are the implications? Without PK, our key management headaches get worse, but there is (almost?) nothing we can do with public key we can't do with private key. The scalability of authentication servers is problematic and the number of keys you keep around on your systems grows, but in practice probably not nearly as much as people fear, since most people really only connect securely to a few places, anyway.

Okay, so can QKD take over the role filled by PK crypto? After all, the physicists talk about it being impossible to break because of the physics. Nope, and for a simple reason: QKD still requires a classically-authenticated channel; that is, it still requires the functionality that Shor broke! It doesn't fix Shor. But, if you have authentication you can trust today, regardless of whether it is PK or not, you're set; the authentication information is not used in the generation of the key used to encrypt the data.

I sat in on a talk on QKD by Todd Brun at ISI's div7, in front of thirty or forty of the planet's best networking researchers. They immediately started jumping up and down and stamping their feet about man-in-the-middle attacks and the need for the authenticated channel. Todd remarked something to the effect that the physicists, if they are aware of the problem at all, are much less cognizant of its operational implications. Paterson et al. wrote a nice paper on the implications of QKD, where much of what I've written here is discussed, and probably more coherently.

QKD's place is for the truly, truly paranoid: people who believe that their traffic is being snooped today, and that classical, symmetric crypto (3DES, AES) will fall to either mathematical advances or some further quantum computing advance sometime in the distant future, and don't want their traffic from TODAY read by somebody half a century from now. Authentication that is good enough TODAY, plus QKD, is good enough to guarantee that your data is safe for all time (modulo breakins/breakdowns at the end points).

In that case, your only operational choice is to use the QKD-generated key as a one-time pad, and discard; if you're really paranoid enough to want the QKD, don't use it to just generate keys for use with a symmetric crypto protocol. That means you need very high QKD bit-generation rates, and most are still in the kilobits/second. Some experiments have been done in the low megabits/sec., but that's pre-filtering, I believe, which costs you at least one order of magnitude in performance. I was at a talk by Tomita-san, one of NEC's QKD experts, just a couple of days ago, and he was talking about an experimental setup over 16km of real-world fiber on telephone poles that did QKD at an average rate of 13 kilobits/second. The most advanced engineering demonstration is the BBN/Harvard/Boston U. network, see some of Chip Elliott's papers.

I arrived at the party a little late to get in on the recent thread at Dave Bacon's Quantum Pontiff blog, but I did throw in my two cents anyway, see the comments here. There was also some discussion on Dave Farber's IP list, see here and search for quantum or Armstrong.