Andrew Hoyer

about

experiments:

(sudoku solver)

(simple fractals)

(cloth simulation)

(numbers to words)

(particle systems)

(quantum cryptography)

(something a day)

(drip sessions)

photos (flickr)

work

flickr (dolinski)

facebook

twitter

linkedin

email

Quantum Cryptography:

This article/guide/tutorial (or whatever you choose to call it), was written as a project for a cryptography course in the winter semester of 2009 (January-April). As such it is very likely that it will become out of date as the technologies and theories involved in quantum cryptography continue to progress. Please take this article/guide/tutorial as-is and be sure to check other more recent resources (particularly when looking at the ongoing concerns section).

The world as it stands today is in a golden age of cryptography as nearly everyone has access to some form of secure encryption. This is mainly due to the spread of public key cryptographic systems through the internet. As has been seen in history even the most secure encryption systems eventually meet their end. Should the day come that the current popular systems no longer provide adequate security, scientists and cryptographers will most likely look towards the science of quantum mechanics and its ability to provide its users with a method of perfect security.

Below I've described the BB84 protocol for Quantum Cryptography (as developed by Charles Bennett and Gilles Brassard in 1984).

The Scenario:

Lets say there are two people, Alice and Bob, who want to communicate some very important information, Alice's grandmother'sf top secret cake recipe, making sure that absolutely no one else can find out the recipe. We should also note that Alice and Bob have an enemy, Eve, and she desperately wants to get her hands on the recipe so as to start up a large chain of cake shops.

Alice and Bob know that Eve is a very determined individual, so no matter how they communicate, Eve will definitely be listening in (phone lines can be tapped, letters and emails can be intercepted, carrier pigeons can be captured... etc). Luckily, Alice is a bit of a cryptography buff and she really wants to try her hand at using a one time pad to encrypt the recipe, this way even if Eve gets her hands on the message it'll be impossible for her to decrypt it.

But with using a one time pad comes the problem of distributing the key to Bob so that he, unlike Eve, will easily be able to decipher the message. In other words Alice is stuck in a catch 22 situation, she would have to share her secret key with Bob in order to share the secret recipe. To solve this Alice plans on implementing a Quantum Cryptographic system.

She knows that Quantum Cryptography isn't exactly what the name suggests, as it isn't actually used to encrypt anything. Rather it is just a solution to the key distribution problem. So really it is more accurate to call Quantum Cryptography Quantum Key Distribution (QKD).

The basis for Alice's QKD system revolves around tiny indivisible units of light that obey the laws of quantum mechanics.

The Quantum World:

I know that quantum mechanics has a stigma of being very difficult to understand, but don't worry we're not going to be getting into the real wacky stuff. All you need to know are a couple properties of light.

Light can be thought of as both a particle and a wave, each obeying a set of physical laws. When light is treated as a wave, there are sets of classical physics equations that govern how it behaves. When looked at as a particle, light acts much stranger as it moves to the statistical approach of quantum mechanics for its explanation. These particles are known as photons.

Though photons have many interesting properties, we're only interested in a couple:

1. They have a unique property called polarization (or sometimes orientation), for the sake of simplicity we will assume there are only 4 different ways light can be polarized.
2. Just the act of observing a photon has the potential to change its polarization. This is crucial to the functioning of quantum cryptographic systems (we'll see why later).

Polarization:	Horizontal	Up-Down Diagonal	Vertical	Down-Up Diagonal
Symbol:

Above you can see the 4 different orientations we'll be using. Next we need to have a way of categorizing the different types of photons. For that we're going to use what are called polarization filters. A filter takes the incoming photons and filters them according to their orientation:

Filter:	Horizontal	Up-Down Diagonal	Vertical	Down-Up Diagonal
Symbol:

So a filter only lets through photons, a filter only photons and so on.

Next we'll look at how to detect them. For that we have two different types of detectors, Rectilinear which detect and photons, and Diagonal which detect and photons:

Detector Type:	Rectilinear	Diagonal
Symbol:

This is where the second property of photons comes into play. We already stated that a detector detects and photons, but what would happen if either of the diagonal photons were to hit the detector? Well as it turns out the diagonal photon will turn into a or photon. So this means no matter what hits the detector, something is always going to be detected. This same idea applies to the detector (it will flip and photons to one of the diagonals).

Input		Filter		Output
	+		=
	+		=

How it works:

The Setup:

For Alice and Bob to pull this off they're going to need quite a bit of special hardware. Lets make a list:

• First off both Alice and Bob are going to need a dedicated fiber optic cable between their houses. The data that is transmitted through Quantum Cryptography is very different from the regular optical data (regular data doesn't care at all about polarization or individual photon counts).
• Alice needs a machine that will produce, as well as filter, individual photons.
• Bob needs a machine to accurately detect individual photons.
• Lastly they need to decide on a convention for describing the individual photons. Lets say they came up with this ahead of time:

  Polarization:	Horizontal	Vertical	Up-Down Diagonal	Down-Up Diagonal
  Symbol:
  Representation:	1	0	1	0

  This is saying that if a or photon is detected, a 1 will be recorded. If a or photon is detected, a 0 will be recorded. This decision is completely arbitrary, so it doesn't really matter who knows this information, all that is important is that both sides agree on the same thing.

The Algorithm:

Lets go through a quick overview of how this whole process is going to work. Don't worry if you don't understand everything right away, hopefully when we look closer at each step you'll understand how it all fits together.

1. Alice, using her photon emitter, sends a random sequence of 0's and 1's by switching between her 4 different polarization filters making sure to note the polarization of each one she sends. This initial string of photons is generally very large. For example, a 250 character message, Alice should initially transmit around 4000 bits, 8 bits/character (assuming ASCII characters) x 250 characters x 2 (because as we'll see, half of these bits will be lost).
2. On the other end, Bob has no idea what types of photons Alice is sending, so he is forced to switch randomly between his two detectors. With every photon he writes down which detector he used as well as the 0 or 1 result.
3. Once Bob is finished detecting Alice's photons, he phones Alice (fully aware that Eve may be listening) and tells her which detectors he used on each photon. Alice either confirms or denies whether or not Bob used the right detector for a given photon. Both make sure to note which ones he measured incorrectly.
4. They now remove all of the bits for which Bob used the wrong detector. They should now have exactly the same bit sequence, and thus a long one time pad key.

Thats pretty much it. Again I understand that some of these steps may seem a little fuzzy or unclear. Next we'll go through each step and see what is going on.

An Example (with details):

I understand that the above algorithm is a little high and dry, so lets go through it step by step and explain in more detail what is actually going on.

Just a couple notes before we start:

• Alice's initial key length is 4000 bits, but at each step I'm only displaying the first 20 bits.
• At every step you have the options to generate new sets of data for both Alice and Bob. In a real life implementation this would never happen, either the whole algorithm is executed, or it is stopped and restarted from the beginning using a new random key from Alice. This is to ensure perfect security.

Step 1:

The first step of the whole process is for Alice to generate her set of random bits and encode them using her different polarization filters making sure to stick with the convention that her and Bob decided upon earlier (that being that 1 is encoded as or and 0 is encoded as or ), sending this sequence through the fiber-optic cable to Bob.

This step may seem rather weird at first, why would Alice send a completely random sequence to Bob? The whole idea of Quantum Cryptography is to generate a very large random key, so it is obvious that for the key to be random at the end, it needs to be random at the beginning. If you want, you can generate another random sequence for Alice.

Step 2:

Now its Bob's time to shine. Remember, Bob has no idea what polarization of photons Alice is sending down the line, so he has to randomly switch between his two photon detectors making sure to record which detector he used and what bit he detected. His results should look something like this:

Again this is where quantum mechanics comes into play. Because Bob has no idea what the polarization of each photon is, he has a 50% chance of using the proper detector, but either way he's going to record a result. For example, say Bob uses a detector for the first photon, if that photon happens to be a or a then he is going to properly record the bit that Alice was trying to send. But if he used a detector, there would be a 50% chance that he'd record the bit Alice was intending. Remember this same idea applies for if he were trying to detect either of the diagonal photons.

If you want you can generate Alice's sequence again, or you could always generate Bob's half.

Step 3:

When Bob is done receiving Alice's transmission, he calls Alice over the phone. Together they go over the whole transmission comparing the detectors that Bob used to what he should have, taking note of which ones he got wrong (outlined in red).

The important thing to remember in this step is that Bob and Alice only talk about which detectors were used properly. This means Alice can't say anything about the random bits or photons she sent, and bob can't say anything about which bits he recorded. If they do let slip some of the bits or types of photons then this whole process has been a waste as you can count on Eve listening in on the phone call, trying to get any information she can.

If you want you can generate a whole new set of data, or a new sequence for Alice, or a new sequence for Bob.

Step 4:

The last thing that Alice and Bob have to do is assemble their final key. To do this they must ignore any bits for which bob used the wrong detector.

Above you can see that Alice and Bob have just dropped the incorrect bits. When all the bits they agreed upon are put together they have their key:

Below I've encrypted the recipe using the key generated above (in combination with an extended Vigenere square). For ease of comparison, I've added a space between every character.

One last time. If you want to, you can you can generate a completely new set of data, or a new sequence for Alice, or a new sequence for Bob just to see how everything changes.

Why it works:

Lets go ahead and look at some of the crucial components of this process and see if there is a way for Eve to get Alice and Bobs key. If we make the assumption that the computers that Alice and Bob use are completely secure, then there are only two areas that Eve can attack:

Alice and Bob's transmission:

I know when I first started learning about Quantum Cryptography I thought to myself, 'Why couldn't Eve just "tap" Alice and Bobs fiber optic cable and read all the photons that Alice is sending to Bob?' Unfortunately for Eve, this is a lot more difficult than it sounds.

One of the key properties of this entire set up is that measuring the polarization of a photon has the potential to change its polarization. So this means that if Eve manages to tap the line and starts taking readings of Alice's photons she might end up changing them. This in turn means that the photons which Bob detects may be different from the ones that Alice sent. Below is an example of what this scenario would look like:

The above table gives lots of information. First off, I've done the usual removing of bits for which Bob used the wrong detector. Next thing to notice is that I've also highlighted the detectors for which Eve used the wrong detector and thus accidently switched one of Alice's photons. Lastly, I've also highlighted the bits for which Alice and Bob did not agree upon (because of Eves meddling).

Lets look at this scenario with a bit of statistics. Because Eve has no idea what orientation of photons Alice is sending, she follows the same procedure as Bob of randomly switching between her detectors. In doing so she is statistically going to get about 50% right and 50% wrong. Bob is going to do the exact same thing, and it turn is also bound to choose the correct detector 50% of the time. Combining these results, on average if Eve measures every single photon that Alice sends, she will inadvertently mess up about 25% of Alice and Bob's final secret key.

So really, all Alice and Bob have to do to ensure the security of their key, is check some of their final bits (and discard them). If a bit does match, then they know Eve is listening in and would abandon the key.

Alice and Bob's Comparison:

For the sake of an example, lets assume that in this scenario Eve did not try to "tap" Alice and Bob's photon transmission and detection. Instead she is just going to listen in when they compare their results and try to learn something about their final key.

So after Alice and Bob finish they're transmission they phone each other. Eve then compiles the table we see below.

Not exactly a lot there... Sure she knows which detectors they used for their key, but what she doesn't know is which photons they detected. This means if she wants to find out the key, she would have to try every possible combination of 0 or 1 for every bit. To put this in perspective, if the final key was say 2000 bits longs this means she would have to check 2^2000 possibilities, a number so large that even Google's calculator can't compute it...

Ongoing Concerns:

Quantum Cryptography as it stands today is not perfect. In this last section I would like to talk about some of the problems that prevent Quantum Cryptography from stepping into public use.

Hardware:

As you can see from the setup of the example above, QKD depends heavily on hardware components. This is probably the largest limiting factor of the system as a whole as it relies on the proper transmission and detection of individual photons. This is no small feat as photons are sensitive particles and if not treated carefully, can change polarization or sometimes disappear.

• Distance of transmission:

  Fiber optic cables today generally have a limited distance of transmission. To combat this, fiber optic networks use amplifiers at certain points to read and boost the signals so that there is no data loss. With a quantum cryptographic system, amplifiers cannot be used for two reason. First normal amplifiers don't care about the polarization of individual photons, so any special polarization before the amplifier would be lost. Second, is that even if there were a way to successfully amplify a photon without losing its polarization, it would provide an entry point for an eavesdropper.

• Emission of single photons:

  Another technical detail is emitting single photons, most systems cannot accurately send individual photons. The problem arises from the fact that photons are actually tiny particles of energy generated by excited molecules. So if when generating photons you accidentally input too much energy you might get several photons out. Many in place QKD systems have ways to combat this, but it is still something that should be noted as it hinders a perfect implementation.

• Dedicated fiber lines:

  Because the quantum cryptographic protocol is so different from regular optical data transmissions, it would require a dedicated fiber network. As the cost of running fiber optic cable can be expensive, it is very likely that Quantum Cryptography would only be used for the most important communication channels (e.g. between governments), not regular civilian use.

• Hardware attacks:

  A more interesting problem is that even if all of the above problems are solved and Quantum Cryptography could be properly implemented, a single paperclip has the ability to destroy any secure communications. By pinching a quantum cryptographic fiber cable between a paperclip, photons passing through the kink in the cable would most likely change polarization. This has the effect of not stopping the transmission from taking place but would destroy any attempt at key generation, thus turning encrypted messages into a mess.

Other cryptographic systems:

Perhaps the most influential reason of why Quantum Cryptography isn't further developed, is that many of the encryption systems in place today seem to be doing the job just fine.

• Flexibility:

  Many public key crypto-systems in use today (PGP and RSA) are readily available and can be used on just about any computer connected to the internet. This alone puts quantum cryptographic systems at a severe disadvantage as it requires so much dedicated hardware. Where as something like PGP requires absolutely no dedicated hardware, just software.

• Current strength:

  Although this may change in the future, the current strength of public key crypto-systems is rather strong. Some systems boasting that breaking a key would take many times the life of the universe. For most communications this should be enough.

Conclusion:

Quantum Cryptography today, if nothing else, is an interesting experiment bridging two sciences. As such it is bound to grow and evolve with time (like any other science), sometimes going in the right direction and other times, not. What ultimately matters is that it is at least something different from the mathematics based cryptographic systems that are prevalent today. Yes, the quantum cryptographic process I've described above has limitations in its physical implementation, but out weighing those limitations is the soundness of the theory of security embedded in quantum mechanics and as such it is the biggest step we have to the holy grail of 100% perfectly secure communications.

Try it out:

Below you can encrypt some text using a key generated with quantum cryptography.

Plain Text:	Type your message here!
Key:
Cipher Text:

Note:

• To use the key generated by quantum cryptography, it must first be converted into ascii numbers. This is done by dividing the key into 8 bit segments, then converting those to decimal numbers.
• The messages are encrypted and decrypted using an extended Vigenere Square.
• It only accepts ASCII characters, it'll strip out anything else.
• Try to break this: 95R/$Cg14HixR"%Uz* Nw#EUI%"M4ake6g7%wJH,|2]#\{b[3!qN_EdMzE4tvJSmb8&

References and Further Readings:

References:

• Singh, Simon. The Code Book. Toronto: Anchor Books, 2000.
• V.K., Stanatuis. “Identifying Vulnerabilities of Quantum Cryptography in Secure Optical Data Transport”, IEEE Security & Privacy, 2007
• Goelm, Rajni et al. "Research Directions in Quantum Cryptography", ITNG, 2007.
• Elliott, Chip. “Quantum Cryptography”, IEEE Security & Privacy, 2004

Further Readings:

• Simon Singh's book, The Code Book, provides a great introduction to the entire field of cryptography and is a great place to start if something on this page has tweaked your interest.
• Wikipedia's Entry on Light Polarization provides a rather hairy explanation of how physicists deal with the polarization of light (not for the faint of heart).
• Wikipedia's Entry on Quantum Cryptography does a just explanation of other cryptographic systems as well as BB84 (as explained here).