Sunday, February 20, 2011

quantum cryptography

Suppose I want to send a message to you in complete secrecy—is there an unbreakable code I could use?

First, notice that any string of symbols can be coded via a string of numbers, and any string of numbers can be represented by a string of 1s and 0s. So, for the remainder of this discussion, let's assume that the message is a sequence of 1s and 0s.

An unbreakable code is provided by the one time pad. This is a randomly generated sequence of 1s and 0s as long as the intended message. If both you and I have access to the same one time pad, then I can take my message and add it to the pad mod 2 (i.e., 1+1=0, 0+0=0, 1+0=0+1=1) before sending it to you. When you receive it, you subtract the one time pad from it to recover the message. If the signal is intercepted, however, it is impossible to decode, because it is completely random, i.e. it contains no information about the contents of the message.

Although a code using a one time pad is unbreakable, it is not necessarily secure. The one time pad must be written down somewhere and communicated from me to you. In the act of getting the one time pad to you, I expose it to interception by whomever we are trying to conceal our communication from.

Is there a completely secure means of establishing a one time pad for us to use?

Before answering this question, let's answer a more general one—is there a completely secure means of transmitting a sequence of 1s and 0s?

One answer is provided by quantum cryptography. Photons (and other quantum particles) have an odd set of properties. One of these, called "spin" has these useful features:

1. It can be measured at any orientation, but at only one orientation at a time.

2. When measured at a particular orientation, there are two possible outcomes ("spin up" or "spin down"), which can only be predicted probabilistically, and therefore constitute a source of randomness if no prior information about the photon's history is available.

3. If the photon is measured again at the same orientation, it will satisfy the same value.

4. If the photon is measured at a different orientation, then it's outcome will again be inherently probabilistic. Furthermore, if, after being measured at a second orientation, it is measured again at the first orientation, it will no longer satisfy the original outcome, but will have returned to behaving probabilistically.

So, suppose I want to send you a sequence of 1s and 0s. I could measure the spin of photons at a particular orientation. If I want to send a 1 and the photon has spin up, I let it stream to you. Likewise for 0. If the spin of the photon disagrees with the digit I want to send, I merely intercept it and prevent it from passing to you. If you know the orientation of my spin measurement machine, then you can measure the photons as you receive them and reproduce my message.

Any potential interceptor who does not know the orientation of our spin measuring machines will get a random signal if he attempt to measure the photons at the wrong orientation. Furthermore, you will know that he has intercepted the message since when you measure the photons at the correct orientation, they will behave probabilistically, instead of reproducing my [meaningful] message.

OK, but suppose the interceptor knows the orientation of our photon machines? Here is where a one time pad would allow us to still send a completely secure message. But how can I transmit the one time pad to you given that our communication channel has been compromised.

Now we reach the beauty of quantum cryptography.

Procedure for transmitting a secure one time pad, courtesy Simon Singh's The Code Book.

You and I use two orientations for our spin measuring devices. We can communicate these exact orientations over an unsecure channel if we'd like—I could simply call you on a telephone and tell you what they are, for example.

Now, I measure a large number of photons, randomly switching between the two orientations of my spin measuring device. You receive the photons and measure them with your spin measuring device, also switching randomly between the two. Obviously, you don't know the random sequence of orientations I used, so sometimes your choice of orientation matches up with mine, and sometimes it doesn't. When it does, you measure the same value for the photon's spin as I did; when it doesn't, you get an outcome which is random and meaningless.

Next, I contact you on an unsecure line (e.g. the telephone), and tell you the sequence of orientations I used. After each one, you tell me whether the orientation you chose at random matches with mine, or not. If they match, we keep that digit; if they don't we simply discard it. This produces a sequence of 1s and 0s that we both know, but are known by no one else. I know them because I measured them, you know them because you measured them. Furthermore, they are completely random because the initial measurement outcomes were random, my choice of orientations was random, your choice of orientations was random, and, consequently, the instances of match between these choices of orientation were also random.

This sequence of 1s and 0s can now be used as a one time pad to send a completely secure message.

What about our eavesdropper? He knows the two orientations we chose, because he can certainly tap our unsecure phone calls. He also knows the sequence of instances in which our choices of orientations matched up, so he knows which photons in the sequence established the one time pad. But he doesn't know from eavesdropping on our unsecure line the outcome of these measurements, so he doesn't know the sequence of 1s and 0s, so he doesn't know the one time pad.

But what if he had tried to intercept this pad-establishing sequence? Since both you and I chose our machine orientations randomly, he could not know this sequence while intercepting the photons. If he likewise chose a random sequence of orientations for his machine, then he would invalidate any of your measurements at a different orientation. But this won't help him decode the message I send—he'll simply

What's the best case scenario for our eavesdropper? He'll be able to decode those characters in my message for which all three of us chose the same orientation of measuring device (the agreement between you and me meant it was added to the one time pad, the agreement with him meant he knows the correct value and didn't convert the photon to gibberish). Assuming we're all choosing between 2 orientations at 1/2 chance, this should only occur 1/2(1/2)(1/2)=1/8 of the time. But you and I are only using digits when we've matched up, so our chances are removed from this equation. Ultimately, he'll potentially be able to decode 1/2 the characters in our message. However, after sending a single message via this method, we'll know there was an eavesdropper, since half the characters will be gibberish.

We can diminish the eavesdropper's ability to decode a single message by increasing the number of possible orientation we switch between. With 3 orientations, he should only be able to decode 1/3 of the characters, with 4, 1/4, etc. Of course, increasing the number of possible orientations means sending a significantly longer string of photons in order to establish the one time pad, but if the process is automated (and the intended messages sufficiently short), this trade-off in time might be trivial compared to the gain in security. In principle, we can reduce the percentage of characters the eavesdropper could decode (again, from the first message sent, since after that, we'll know he's eavesdropping) indefinitely.

No comments: