Quantum Cryptography

Doc Rampage has this to say about one-time pads:

The problem with one-time pads is that the pad contains as much information as the message and it requires a fully secure channel because if anyone can intercept the pad, he can easily decrypt the message. If you have a fully secure channel with enough bandwidth for the pad, why not use it to send the message? One-time pads are really only useful when you have two channels, one secure and one insecure, and you don't always have the secure channel available. Usually the non-secure channel is a wide-area network and the secure channel is some guy on a plane carrying a CD. In these cases, you can use the secure channel to send the pads whenever you can and you use the non-secure but faster, more reliable, or more widely available channel to send the messages.

This seems like the perfect time to talk about quantum cryptography, or as it's more accurately known, quantum key distribution, which proves once again that there's an exception to every rule, and it's quantum mechanics. The idea is to distribute some amount of data which will be used as the key to encrypt the message you want to send. So this data you exchange, the key, is the equivalent of a one-time pad, distributed securely. Why not just send the message this way? Well, as we'll see, QKD is very inefficient, and only a quarter of the data gets through, which would be pretty useless if you were sending message data. It's also vulnerable to eavesdropping; the trick is that you can tell when it's being eavesdropped.

Let's say you have a public channel, which can be eavesdropped. One party, Alice, wants to send a message to another party, Bob, but is worried that it could be eavesdropped by a third party, Eve. (These are the standard names used in the quantum key distribution literature.) However, this channel is capable of carrying not just regular bits, but also qubits. This is simple enough to imagine, since sending individual photons in essence sends qubits down the channel. Photons also make it easier to explain how the process works, so we'll stick with that. Alice's photons are linearly polarized, in 4 different directions, 0 degrees, 90 degrees, 45 degrees, and 135 degrees. If you use a polarizing filter, then orthogonal light can't get through the filter. If your filter is at 0 degrees, then the photon doesn't get through if it's at 90 degrees. However, due to the magic of quantum mechanics, a photon polarized at 45 or 135 degrees has a fifty percent change of getting through since you can decompose it into a 0 degree and a 90 degree component. Similarly, a 45 degree filter will block 135 degree polarized photons, but pass 50% of the 0 and 90 degree photons. There's no way to tell what the original polarization was. If you have a 0 degree polarizing filter, and a photon gets through to your detector on the other side, then it may have been polarized at 0 degrees, or it could have been polarized at 45 or 135. If the photon is blocked, then it may have been polarized at 90 degrees, or at 45 or 135. So we have two sets of two polarizations which are orthogonal to one another (0-90 and 45-135) but not orthogonal to the other set.

Alice takes a string of random bits, a, and decides on the polarization from a equal-length string of random bits b. For the kth bit in each string, if a(k)b(k) is 00, then she sends a photon polarized at 90 degrees. If a(k)b(k)=10, she sends a photon polarized at 0 degrees. Using a 0 degree polarizing filter with a photodetector on the other side, measuring a photon indicates that a(k) is 1 and measuring no photon indicates that a(k) is 0. If a(k)b(k) is 01, the photon Alice sends is at 135 degrees, and if a(k)b(k) is 11, the photon is at 45 degrees. So if b(k) is 0, the photon should be measured with the 0 degree filter, if b(k) is 1, it should be measured with the 45 degree filter. However, neither Bob nor Eve have any way of knowing this. Instead, Bob randomly chooses the filter with which to measure, using random string b'. The results of the measurement gives a string of a'. If there's an eavesdropper, Eve, she can also try to measure it, but there's no way to measure a photon and then send it to Bob. It's also not possible to copy a photon exactly and measure the copy. Eve could try measuring the photon by guessing at the correct polarization, then send a new photon to Bob based on her guess. If she guessed that the photon would be either 0 or 90 degrees and used a 0 degree filter, she could send Bob a new photon at either 0 or 90 degrees based on her measurement, and if she had guessed correctly, the photon would be at the correct angle. However, if she guessed incorrectly, it would be at the wrong angle. If Bob also measures with the 0 degree filter, it won't make much difference, so if Alice, Bob, and Eve all used the same polarization (a 1 in 4 chance), Eve would have successfully eavesdropped. If Bob measures with a 45 degree filter and the original photon was in the 45-135 set, while Eve measured and resent at 0 degrees, then there's only a 50% chance he'll get the correct value.

Once Bob tells Alice he's gotten the message, the two compare their b and b' strings. This is done publically, so Eve can hear what's being said. They then toss out all the bits where b and b' disagree, where Bob measured at a different polarization than Alice sent, since for each of those bits a(j)=a'(j) only 50% of the time. All the remaining bits should agree. So next they randomly choose about half the remaining bits to compare. There'll probably be some errors just due to the difficulty of sending single photons over long distances, but if the error rate exceeds a certain threshold, then they can know that someone's been eavesdropping on their communication. In that case, they can scratch the attempt and try again. (However, if Eve was smart, she may have eavesdropped only a small number bits, thus settling for a partial key while keeping below the threshold error rate.) If they decide they weren't eavesdropped, they need to correct for errors in the transmission by information reconciliation. Information reconciliation is a form of error correction, doing parity checking on random subsets of the shared string (a and a'), discarding the last bit each time so that Eve gains no new information (a parity check of a set of bits sums all the 1s and determines whether the result is odd or even; any single bit in a set can change its parity, so if you discard a bit without disclosing its value, you reveal no new information by revealing a set's parity). The subsets are chosen to be small enough so that each is unlikely to contain more than one error, and if an error is found, the subset is bissected and the parities checked again until the error is located. This is done repeatedly, with different, randomly chosen subsets, to negate mistakes caused by selecting subsets where an even number of errors may have given a false parity check. Let's say this is done, but Eve still has some information about the key--not a lot, else they would have detected her. Information reconciliation neither increases nor decreases the amount of information Eve has, since if you discard a bit she knew, she then learns what the parity of the remainder of the subset is. Privacy amplification reduces the information available to Eve, even if she's intercepted some information, while reducing the total number of bits in the key. One way of doing this would be to publically select a permutation of the remaining bits in a=a' (without sharing any of the values), then divide it into blocks of a certain size, and using the parity of each block to form the new key. This is a pretty inefficient way of doing it, where the total number of bits in the new key, r, equals the original number of bits divided by the block size. However, it drastically reduces the amount of information that Eve has, since Eve only knows the parity of a block when she has all the bits in it. There are more efficient functions, but the smaller the final key is compared to its original length, the less information available to Eve, even if she managed to get some information from eavesdropping.

The remaining bits form the key, which can then be used to encrypt the message Alice wants to send. Depending on degree of privacy amplification (how much you're willing to reduce the key size) and the error threshold (how many errors you'll accept before concluding that someone's eavesdropping), the distributed key can be made arbitrarily secure.

One thing you'll notice right away is that QKD is very inefficient. Even before information reconciliation and privacy amplification, you're down to about one-fourth the number of bits you started with. However, you can't expect any provably secure communication over a public channel to be efficient. This form of quantum cryptography (there are others, different in details but similar in concept) has been demonstrated in a lab environment, and at distances of up to 100 km. This particular application of quantum information is in the early stages of commercial application.

I didn't write all of this from memory, although I have studied it before. I needed to look up the details, so I used Nielsen and Chuang's Quantum Computation and Quantum Information, and this useful website.

Update: Doc Rampage gives a... uh, simpler explanation. Also, I edited for clarity.