The ins and outs of quantum cryptography

This post is based on a conversation with Bill Munro from HP Labs.

One of the few uses for quantum information theory which is accessible using existing technology is quantum cryptography or quantum key distribution (QKD). QKD gives us a means by which to - in principle - share random bit strings with complete security, by which we mean that any attempt to eavesdrop on the communication can be detected and there is no way of circumventing this. So what's the use in sharing a random bit string with someone? There is only one completely uncrackable encryption protocol, known as the one-time pad or Vernam cipher. By 'completely uncrackable' we mean that - hypothetically speaking - even with infinite computing power at one's disposal, it is not possible to crack. The one-time pad protocol relies on a completely secure random bit string as a resource. The caveat is that the random bit string must be as long as the message being encrypted. For this reason the one-time pad is rather impractical in most situations, since if we had the means by which to securely share a random bit string we could have just used it to share our secret message in the first place. QKD solves this problem.

There have been many experimental demonstrations of QKD over increasingly long distances and recently commercial cryptography systems based on QKD have become available, most notably by MagiQ. Companies which manufacture commercial QKD systems tout the incredible security of QKD which is 'guaranteed by the laws of physics'. In principle such a claim is correct. However, Bill drew my attention to a very interesting point recently. The rate at which commerical QKD systems can communicate random bit strings is very slow - on the order of a hundred bits per second. Since the one-time pad requires a random bit string as long as the message to be encrypted, it should be clear that such a system is not going to be useful for anything but the smallest messages. For this reason, these systems don't actually employ the one-time pad algorithm at all. Instead they employ conventional cryptographic protocols such as triple-DES and AES, which require much smaller keys. Of course this completely undermines the security of QKD, since QKD inherently derives its security from the fact that the one-time pad is the only completely secure cipher.

When I first learned this I was extremely surprised, since, while it may not be explicitly advertised, it is taken for granted that any QKD system will employ the one-time pad cipher. My take on all this is that customers of current QKD systems are paying hundreds of thousands of dollars for cryptosystems no more secure than freely available software packages like PGP.

2 thoughts on “The ins and outs of quantum cryptography”

  1. > My take on all this is that customers of current QKD systems are paying
    > hundreds of thousands of dollars for cryptosystems no more secure than
    > freely available software packages like PGP.

    I think that’s a tad unfair — PGP relies on an asymmetrical algorithm for its KD, and therefore is relatively more vulnerable than QKD. Security isn’t all or nothing — there’s more secure and less secure. Calling QKD 100% secure is disingenuous on a few levels, but it’s still much better than current methods.
    The weakest link in QKD, instead of being the exchange algorithm, is in the key itself. So to partially combat the weakness, they exchange a new key every several seconds or so.

    If you were doing RSA based exhange with time sensitive transactions, and someone deduced your private key, then all subsequent transactions would be insecure — which means they could impersonate you in real time, and intercept everything as it happens.

    With QKD, the time to crack a symmetrical encryption algorithm with the world’s fastest supercomputer needs to be greater then the key refresh rate….assuming that time sensitive transactions are taking place, i.e. date stamped electronic transfer of money from the federal reserve or something, which would be fairly useless to a hacker a day later.

    If messages like “kill Castro on Tuesday” are being sent, then obviously the user would never want these to be intercepted — so it would probably be good if QKD systems had a special one-time pad mode for short, vital messages.

  2. I agree with your comments. Specifically, for time-sensitive transactions, where it doesn’t matter if someone can determine the plaintext at a later time, present QKD systems will still offer a significant security advantage.

    I agree also that perhaps PGP wasn’t the best comparison to make, since here the weakest link is the asymmetric crypto protocol rather than the symmetric one. The only point I was trying to make was that by using QKD to share keys for AES or 3DES based encryption reduces the level of security to the inherent security of these algorithms.

    On your last point, according to the MagiQ datasheets, their systems do in fact have a one-time pad mode. Needless to say however, as you point out, this mode of operation would only be suitable for very short ASCII messages and not for the bulk of what’s being encrypted.

    Another point, which I didn’t mention, is that commercial QKD systems don’t actually implement ‘true’ BB84, since they don’t have true single photon sources. Instead they use attenuated coherent states which, at least in principle, introduces some room for intercept attacks.

    Note: Refer to Jon’s follow up blog-post on this issue here.

Leave a Reply