Wednesday, August 20, 2008

Cracking Quantum Cryptography

There must be some error in my thinking here, but it seems to me that quantum cryptography has been over-hyped as being ultra-secure.

The idea of quantum cryptography depends on producing a pair of entangled photons. These are photons that have indeterminate polarization, either horizontal or vertical, say. But until they are inspected, it is not known what polarization they have, and indeed, according to quantum theory, they have no particular orientation until they are examined.

Being “entangled” means that when one member of the pair is examined, its orientation is at that moment determined to be randomly H or V, and automatically and instantaneously the same orientation is determined in the other member of the pair, no matter how separated the two are in space. Quantum entanglement is a well-documented phenomenon.

In Quantum cryptography, each member of a pair of entangled photons is sent to a different person. When Alice examines her photon and determines its orientation (H or V), she is assured that Bob’s photon has exactly the same orientation, because the two photons are entangled.

The change in status from indeterminate to determinate takes, literally, no time at all, which is how Bob’s photons manage to instantaneously match their entangled partners in Alice’s shop, across any amount of space.

Alice does the same on the next photon she receives. Each time this process is repeated, she records H or V orientation for the photon, lengthening her string of random, binary choices which becomes the encryption key.

The string of binary values (which could be represented as 1s and 0s) is random, and both Alice and Bob have the same string. Alice can encrypt her secret message with that key and confidently send it to Bob in ordinary email. It would be impossible in principle for anyone except Bob to decipher the message, since it is based on a random key.

How this technology differs from ordinary public key cryptography is that Alice and Bob do not have to share the key in advance. Having a shared key is less secure because such a “key” is typically a mathematical algorithm executed by a computer. Both parties know what that algorithm is. However, with a big enough computer and enough time, any such key can be cracked. With a quantum key however, there is no algorithm. The key is utterly random.

It is impossible to decipher the encrypted message without the quantum key, so you wouldn’t even try. Instead, you would attempt to intercept the key as it was being sent to Alice in the first place. Once you had Alice’s key, you could easily decipher her secret message to Bob.

If “Eve,” eavesdropped on the stream of encrypted photons headed for Alice, then Eve would have a copy of Alice’s key. But the photons would not look any different to Alice. They were always H or V at the moment she looked at them before, and they still are.

The standard answer to this attack is to note that Eve’s interception distorts the information encoded in the photons’ orientation in some way. I have no idea why that would be, especially for the “E91” protocol described here, where Alice and Bob each get one member of a very simple entangled pair.

In the articles I have read, it is just asserted that Eve’s interception would be detectable somehow. Probably the explanation involves some arcane physics or mathematics that I could not understand, so it is just as well that these articles do not say what errors Eve would introduce into a photon when she examines it. Let’s just assume that she does distort the key in some way however.

Nevertheless, Alice has no criterion for determining whether her quantum key has been tampered with or not. They are all just photons to her. If she were to compare her key with Bob’s, they would jointly determine that they did not match, since Bob’s photons had been previously disentangled by Eve, not by Alice.

But how are they going to compare the quantum keys? By sending them in an email? That wouldn’t be very secure. It defeats the whole purpose of the exercise. They cannot compare the keys prior to having secure keys with which to communicate. It’s a chicken and egg situation.

It’s true that Bob will not be able to decode Alice’s message, since their keys do not match, but Alice does not know that. So she sends her secret message by email, Eve eavesdrops on it, decodes it with her key that matches Alice’s.

Bob will realize that he cannot decode Alice’s message and will call Alice to let her know, and they will both realize there had been an interception. But by that time it is too late. Eve has the secret message.