Author: dabacon

Via Michael Nielson’s blog, I’ve learned that Scott Aaronson has strated a blog: Shtetl-Optimized. Since Scott is essentially crazy (that’s a complement, peoples) I’m really looking forward to his posts. Plus he said he will talk about the Simpsons, and heck, who doesn’t like talking about the Simpsons?

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.

John Preskill points me to Workshop on Classical and Quantum Information Security to be held December 15-18, 2005 at Caltech:

This workshop will bring together researchers from a variety of backgrounds who work on different aspects of classical and quantum information security. Participants will strive to identify issues and problems of common interest that can be effectively addressed by pooling their expertise.

Looks like a very broad spectrum of researchers will be attending, which should make for a very interesting workshop. Overcoming communication barriers is often the first step in interesting new research directions, and I’m sure one hope of the workshop is to aid this difficult process.
Which reminds me of a documentry I saw a few years ago which tried to identify why certain schools were much better at producing (not buying 😉 ) Nobel prizes. What the documentry argued was that the common theme for the top Nobel producing institutes was that they all had very loose definitions of what was considered “in a particular discipline.” Or, the way I like to think about it: the energy landscape on the space of different research programs had very shallow minimums at the top Nobel producing institutes, whereas at most other schools, these wells were very deep…sometimes being even infinite square wells! This is, of course, an oversimplification, but I’m glad to see that Caltech (highest Nobel prize count per member of the community that I know of ) is hosting a workshop which so well imbodies this spirit.