Sunday, January 16, 2005

Quantum Cryptography involves using quantum mechanics to detect eavesdroppers. This technology will soon be available in commercial products. Something I haven’t figured out is how well practice will match theory.

In theory, you send each bit once and you can detect eavesdropping because the bit will be destroyed when the interceptor reads it. In practice, non-quantum networks have to handle bit errors, and I would expect quantum networks to have to do the same. They might use error correcting codes, retransmits, or other approaches, but they have to handle the loss of some number of bits. Given that, can’t I, as an attacker, steal enough bits so that both I and the intended recipient can reconstruct the original message? As I steal bits, it will merely look like the network is having some trouble, but the messages will still get through.

How many bits can I steal?

If I steal every bit, half the bits will be corrupt. If the recipient can deal with 50% bit loss, then both of us can read the error. But if you only need 50% of the bits, then I don’t have to steal every bit. So let’s suppose X% of the bits are required to reconstruct the original message. Half of these will be corrupted as I (the attacker) reads them, so the original recipient will get 100-X/2 % of the bits. If that’s greater than X, then I can eavesdrop without destroying the original message. This comes out to 33% packet loss.

I don’t know how the recipient is going to distinguish between a clever eavesdropper and the network problems that happen all the time. Given that the hardware or software normally transparently hides those errors from you, you will never see anything that looks like an eavesdropper. If the network + error correcting algorithms can handle loss of 1/3rd of the bits, then the eavesdropper can read the entire message by reading 2/3rds of the bits and 2/3rds of the bits the message will still be seen by the recipient, so both will see the message. Quantum cryptography vendors will need to say that they can’t handle too many bit errors.



Anonymous wrote at Sunday, January 16, 2005 at 6:29:00 PM PST

But if Quantum Encryption is used only for (say ssh) key exchange, then we can get away with putting maybe 5% network loss as the threshold and regenerate the key if loss exceeds that figure.


Amit wrote at Sunday, January 16, 2005 at 9:15:00 PM PST

That's a really good point. It's easier to steal the key if you retransmit the same key, but if you regenerate a new key every time you can be safe.