Rod Van Meter has an interest post up today on his blog titled Stop the Myth: QKD doesn’t fix what Shor broke. Along similar lines, Rod points to the paper quant-ph/0406147 by Kenneth G. Paterson, Fred Piper, and Ruediger Schack, “Why Quantum Cryptography?”
Here is my take on what Rod and quant-ph/0406147 are arguing (but I’d recommend reading what they say, because my expertise on quantum cryptography goes to zero in the limit of the people who know what they are talking about going to some number greater than four.) Mostly I’ve just cobbled this together from what Rod said and my own personal misunderstandings. So you should read Rod’s post first, and then laugh at my silly rehashing of the main points.
To simplify life let’s break secure communication into two steps. The first is authentication and the second is key exchange. In most applications what we need to do is first authenticate our channel and then second we need to do key exchange using this authenticated channel. Now Shor’s algorithm broke the most popular public key cryptosystems (those based on the difficulty of factoring and discrete log.) These public key cryptosystems were often used for both authentification and for key exchange. Thus Shor broke both of these when operating with those cryptosystems.
OK, now what the quantum cryptography (QKD) do? Well what it does is, given an authenticated channel, it allows you to create secret keys whose security is based on quantum theory being a correct description of nature. But how does one establish this authentification? Because Shor broke the most widely used public key cryptosystems, we need to establish this with some other technique. One way to do this is for the parties to share some small secret keys which they can then use to establish the authenticated channel. So the point Rod and others are making is that QKD doesn’t provide for an authentication scheme whose security is based on the quantum theory. Rod thinks that physicists haven’t known about this or realized it’s importance, which may be true as I can’t read other physicists brains or listen to all they, but I certainly think everyone working in quantum cryptography realizes this (and even some people who don’t like me 😉 ) QKD is thus best viewed not as a way to providing a total solution to unconditional security but as a way to take a small secret key and use it to create a huge shared secret key. The security of this will be based on (1) the security of the authentication scheme and (2) the laws of quantum theory. Maybe to put this into simple words, I would say that QKD fixes only part of what Shor broke.
Another important point is that in the above paragraph I’m talking about using QKD as a way to distribute keys at a sufficiently high rate to use these keys as one time pads for communication. Right now, many of the QKD systems do not opperate at speeds fast enough to achieve this goal for reasonable communciation rates. Certainly getting to these high speeds is one of the grand challenges in experimental QKD! Currently, I am told, that many QKD systems sold use the keys they generate as part of another layer of cryptography (like 3DES or AEA). This does provide security, but weakens the security (one could conveivably break these other systems…one would need to do this for the size of the key the QKD creates: so as QKD rates go up and up, conceivably one should be able to make this security higher and higher until eventually you will just want to use the key as a pad.)
But, like I said, my understanding of this is murky, so go read Rod’s blog and check out quant-ph/0406147! Oh, and for all you lurking quantum cryptologists, I’d love to hear your take on all of this.
O brave new quantum world!
Hmm, I guess I should go back and revise my text a little :-). I certainly didn’t mean to imply that physicists don’t understand the need for the authentication channel. But I’ve now been to half a dozen QKD talks by physicists, and the authenticated channel is sometimes given one sentence late in the talk, sometimes not mentioned until Q&A. The people working in QKD, as you say, are all aware of it, they just don’t emphasize it much (and consequently, I think many casual listeners are unaware of it). A network security person would probably start a talk on it with, “QKD uses entangled photons and an authenticated channel to…”
So it’s really a matter of focus. The physicists are interested in the physics, the network people are interested in the network. Hmm, now there’s a profound observation…
I certainly agree that the matter of having an authenticated channel along with QKD should be mentioned up front! Certainly if I were talking to a group of experts in security. Maybe the problem is the usual audience those who deal with QKD are used to is rarely this group and so introducing this so early seems confusing.
Well, I always mention it.
Basically Dave is right: QKD fixes part of what Shor broke. Or more correctly, classical cryptography was already broken, Shor just happened to be the one that saw the cracks. There are two additional points I think are worth making:
First, it is a good idea to make a distinction between what QKD does and what quantum mechanics does. There are other possible quantum cryptography protocols besides QKD, and we don’t yet really know to what extent they can substitute for other useful aspects of public key cryptography (like digital signatures).
Second, even without additional quantum cryptographic techniques, authentication is a much easier problem than public key encryption. Indeed, there are reasonably good private key authentication schemes which work with small keys and information-theoretic security (see: Wegman-Carter). The certificate authority system is nice because the CA can sign the public key in the distant past and then be uninvolved, but that’s not really an essential part of the system. It would work nearly as well if Alice and Bob authenticated messages via the CA in real time. Each would start with a shared secret key with the CA, so, for instance, Alice would authenticate a message to the CA, and then the CA would authenticate it to Bob. There is a slight increase in trust required vs. the usual CA model, but the CA can’t learn the message without an active man-in-the-middle attack, which risks discovery and the consequent ruin of the CA’s business.