The use of quantum computation to perform cryptographic functions.

While classical cryptography employs various mathematical techniques to restrict eavesdroppers from learning the contents of encrypted messages, in quantum mechanics the information is protected by the laws of physics. In classical cryptography an absolute security of information cannot be guaranteed. The Heisenberg uncertainty principle and quantum entanglement can be exploited in a system of secure communication, often referred to as "quantum cryptography". Quantum cryptography provides means for two parties to exchange an enciphering key over a private channel with complete security of communication.

Originally theorized by Stephen Wiesner in the late 1960s.

The encryption system generically called quantum cryptography is really the quantum transmission of a one-time pad. In this system, two end points are connected by a physical medium (copper wire, fiber optics) over which the transmission of particles with quantum state is possible.

Let's call these two end points Alice and Bob. Alice wants to communicate with Bob, and has a message of N bits to send. Alice is, however, afraid that Lucy will get her hands on this message, so needs to encrypt it. It needs to be a one-time pad, because Alice really wants forward secrecy, and wouldn't get that if she used PGP. Fortunately, Alice and Bob have a copper wire between them, and the ability to set spin on electrons.

Alice generates about 6*N bits of random data (not pseudorandom), and splits it into two streams. The first stream will be the one time pad; the second stream is her encoding stream. Alice will now encode her one time pad into electron spins, using four spins, effectively:

  • Vertical: | : one-time pad value of 1, encoder value of 0
  • Horizontal: - : one-time pad value of 0, encoder value of 0
  • Right diagonal: / : one-time pad value of 1, encoder value of 1
  • Left diagonal: \ : one-time pad value of 0, encoder value of 1
Alice now sends the stream of encode bits to Bob.

Bob now randomly guesses, for each bit, whether the encoding bit was 0, or 1. If he thinks it was zero, he uses a "+" filter. If he thinks it was one, he'll use an "x" filter. Here is the neat part: If he guess wrong, the spin will rotate - with 50% probability in each direction - to be able to pass through the filter. He then tries to pass the bit through another filter (an appropriate | or / filter will do); if it passes through, the value is 1. If it didn't, it is zero (the spin will not rotate 90 degrees).

Bob now has a stream of bits, about half of which, because he guessed wrong, are useless. To determine which half, he sends to Alice - in the clear, on an authenticated channel, the list of guesses he mades. On the same channel, Alice tells him which ones were right. Bob discards the rest of the bits. For added safety, he verifies the parity of every m bits, discarding the mth bit.

Because the act of reading the stream alters it, Lucy cannot read the stream and forward it to Bob. Because Bob is guessing randomly, and doesn't reveal his guesses until after he has read (and destroyed) the datastream, the probability of Lucy correctly guessing the same bits that Bob would correctly guess is 21.5*N -- highly improbable.

In a human society composed of over six billion individuals, it is impossible that any one person will know and befriend a significant portion of the rest of the people on Earth, yet with our newly developed global communication networks, it is possible that a significant portion of the rest of the world will have access to the information one person is sending or receiving. Because people generally mistrust, if not loathe, those whom they do not know, the person who is communicating, hereafter referred to as "Alicia," very often must keep her information secret from the faceless masses who could potentially be trying to listen in on the answering machine message she is leaving for her cat, Roberto, while she is on vacation. This is why we have developed data encryption, which can save us from the horrible embarrassment of having videos of us trying to emulate the light-saber fight from The Empire Strikes Back being distributed to our co-workers, or our plans for our newest biological warfare strain of smallpox being acquired by nations who do not embrace free-trade economics.

So, Alicia has to decide how to encrypt the data she want to send to Roberto. To do this, both Alicia and Roberto must have encryption keys. Alicia's key must encode the message, and Roberto's must decode the message. The standard methods of encryption used today usually use, at least in part, two different keys, Alicia's being a publicly available one, and Roberto's being a private (ultra top secret) decoder key. The secrecy of the transmitted message relies on the third party, Alicia's arch-nemesis Evita, being too stupid to solve the math involved in deriving the private key from the public one. This is all well and good, except that in this brave new world we live in, Evita may have a Commodore 64 or some other machine of unfathomable computational power, which could easily derive Roberto's private key. In fact, even if both keys were kept completely private, if Evita has by some insidious means acquired a some sort of super-intelligent robot, such as a 486, she could analyze multiple encrypted messages and derive the encryption algorithm. There is, however, a way to beat Evita's vast army of mechanical fiends. This method is known as the One Time Pad (OTP), and it has been theoretically proven to be completely secure and robot-proof.

The OTP method involves using only one key, that both Alicia and Bob, but absolutely no one else, know. They must use this key only once, which is fairly obvious considering this method's name. The key must be at least as long as the message Alicia wishes to send, and it must be generated completely and truly randomly (This means you can't generate an OTP using the Rand function on your Ti-83). This key is used both to encrypt and decrypt the transmitted message. For example, if Alicia wants to tell Bob 1001, and the randomly generated key is 0101, then Alicia could exclusive or (XOR) the message with the key and get 1100. This would be transmitted to Roberto, who would XOR 1100 with the key and get 1001, the original message. This is all well and good, except for the problem of how to generate a truly random and truly secret key that both parties know. Obviously Alicia could generate the key and then take it directly to Roberto, but then she might as well just hand him the message right there. This is where we can take advantage of the quantum mechanical properties of particles such as photons or electrons.

Quantum Cryptography is the single process of using the physical properties of quantum particles to both generate and transmit a secret one time pad. First I will describe the process, and then discuss the quantum mechanics. The most common method quantum key generation works by transmitting information via individual, polarized photons. To do this, we need four different possible polarizations for the photons which must comprise two sets of two orthogonal polarizations, such as Set A = (0, 90) degrees,and Set B = (-45, 45) degrees. We must designate bit values for each possible polarization. Both sets must have both a 0 and a 1. Let's say that 0 and -45 degrees correspond to 0, and that 90 and 45 degrees correspond to 1. The sender, presumably Alicia again, will send one photon at a time, the significance of which I will explain later, and she should randomly choose and then record the exact polarization of this photon by rotating the polarizer on her laser. When this photon reaches Roberto, he will randomly try to measure the photon in (Set A, 1) or (Set B, 1) by altering his polarizer between 90 and 45 degrees. If he measures that a photon passed through his polarizer, he records a 1, and if none passed, he records a 0. If he chooses the wrong set, then he will have a 50 % probability of measuring the photon, because 45 degrees is halfway in between 0 and 90 degrees. He will have this same probability no matter if Alicia's value was 0 or 1, as long as he is using the wrong set. However, if Roberto uses the right set, he will get the same bit value as the one Alicia has, because the photon will only pass through if Alicia used a bit value of 1. This means that when Alicia and Roberto's set value corresponds, their bit value must also correspond, no matter which particular bit value Alicia chose, and that when their set does not correspond, approximately half the bit values will also not correspond. Here is a logic table:

| Alicia's Polarization |  Roberto's Polarization  |	Roberto's Measurement	|
|-------------------------------------------------------------------------------|
|	A 0             |	   A 1             |	   0	                |
|	A 1             |	   A 1             |	   1	                |
|	B 0             |	   B 1             |	   0	                |
|       B 1             |	   B 1             |	   1	                |
|	A 0             |	   B 1             |	   0 or 1	        |
|	A 1             |	   B 1             |	   0 or 1	        |
|	B 0             |	   A 1             |	   0 or 1	        |
|	B 1             |	   A 1             |	   0 or 1	        |
--------------------------------------------------------------------------------

Therefore, after sending numerous photons in this manner, Alicia and Roberto can call each other up on a public phone line, and figure out for which photons they have the same Set recorded. They can then disregard all photons for which they used different sets, and without ever actually saying the bit values of the photons they agree upon, they know that the bit values must be the same in each of their records, because they agree upon the set. This set will then be used as a one time pad. They must also, however, tell each other the bit values for a small number of the photons they agreed upon, to make sure that the bit values are the same. If they are not the same, they know Evita was listening in. How? This is where the use of a single photon for each bit is key. If Evita intercepts the single photon, and measures it, she has to attempt to measure it with A1 or B1, just as Roberto would, but once she has done this, she has potentially altered the photon, thereby preventing her from transmitting the same photon back to Roberto. If she uses the wrong set, which she is 50% likely to do, then she alters the photon that she will then send on to Roberto, and she cannot know if she was using the right set until she eavesdrops on Roberto's and Alicia's conversation about which sets they used. Because the photon sent to Roberto was altered from the photon sent from Alicia, when they check to make sure they have corresponding bits, they will see that someone has been messing with their photons. If however, one were to attempt this type of key generation using a beam of multiple photons, Evita could simply divert two of the photons from the beam, and measure one with Set A and one with Set B. She could then let all the other photons go on their merry way to Roberto. Roberto and Alicia would not know anyone eavesdropped, and Evita would have a record of the bit value for every possible agreed upon photon. This would not do, so single photons must be used. Using this method, both Alicia and Roberto, who can be located far apart, have an identical copy of a completely secure random string of bits, which is the ideal one time pad encryption key.

When one tries to think of ways to eavesdrop effectively and undetectably on this system, the natural method that first comes to mind is to simulate a many-photon system. To do this, Evita would have to make identical copies of the photon sent by Alicia, and then proceed as she would if Alicia and Roberto were using flashlights instead of single photon lasers. However, this is impossible.

To be able to clone the exact state of a photon with an unknown state, would have all sorts of bad implications, including being able to go back in time. This can be shown with entangled particles. Quantum entanglement is the phenomena of two particles' quantum states being dependent on each other. The simplest example of quantum entanglement can be seen with particle spin, or angular momentum. If there is a large particle with zero angular momentum (no spin) , and it decays into two smaller particles with quantum spin, conservation of angular momentum tells us that that the spin s of the smaller particles must be in opposite directions of each other, in order to give a total zero angular momentum. The spin of either small particle is still randomly up or down, however, if we measure the spin of the first small particle and it turns out down, we know we have set the spin of the second small particle to up. A somewhat more complicated process can also produce photons with entangled polarizations. With entanglement of polarizations, two entangled photons are in the same polarization, though the specific polarization is undefined until measured.

To prove that there is no cloning, let us give Alicia and Roberto a set of entangled photons, and assume that Roberto has the superpower of quantum-state cloning. Let's also assume Roberto uses his powers to clone his entangled photon into a whole mess o' entangled photons. Alicia then runs her photon through a horizontal polarizer. Let's say the photon goes through the polarizer, so her photon is now horizontally polarized, which means all of Roberto's photon's are also horizontally polarized. Roberto measures half of his photons along a 45 degree polarization and half along a horizontal polarization. Those which he measures using the 45 degree polarizer will have a 50% chance of going through, but those he measures with the horizontal polarizer will have a 100% chance of passing. Therefore, if he uses his whole mess o' clones, he can see that Alicia has horizontally polarized her photon. The same process works when Alicia uses a 45 degree polarizer, so Roberto can determine instantaneously whether Alicia was using a slanted or a horizontal polarizer. This is transmitting instantaneously, which is, if Alicia and Roberto are in different positions, faster than the speed of light. This would mean that event A (Alicia's action) would influence an event in the past (Roberto's measurement). I could go into this further, but I'll just state that this shows that making a whole mess o' clones violates a whole mess o' established laws of physics. Therefore there is no cloning. Going back to where I started, this means that if Evita wants to know anything about that photon that Alicia sent, she's going to have to mess it up, and when Alica and Roberto are talking later, they're going to find out what's been going on, and they will know that the key they generated is bogus. That is why quantum key generation is completely secure.

However, the method I described is not entirely secure unless Alicia's choice of polarizations is truly random. Generating random numbers can be accomplished by measuring unknown photons, so in order to combine the two processes, many real quantum cryptography systems have a source of entangled photons in between Alicia and Roberto. Alicia and Roberto then both make measurements as Roberto did in my example, and the rest of the procedure is the same.

When I first heard about this method of generating a one time key. I thought that despite its unbelievable coolness, it must be almost completely theoretical, and that no one would have accomplished it outside of the unrealistic confines of a physics lab. It seemed to me, that generating a key would take a very long time. Alicia and Roberto have to throw out half their bits, prevent stray photons from interfering with their measurements, and generate an encryption key at least as long as the entire message they want to be encrypted. Doing this over any appreciable distance seemed nigh impossible, and I had strong doubts. But soft! What light through the National Institute of Standards and Technology's Colorado laboratory window breaks?* It is single photon laser light, traveling over 700 meters to the window of another laboratory for use in the fastest quantum key generation accomplished (As of May 2004). They transmit their photons through open air, preventing noise by turning their photon detector (Roberto) on only at the precise moment they expect a photon from the transmitter (Alicia). Amazingly, they have achieved rates of up to one million bits per second. Admittedly, compared to standard wireless communications that is not very good, but it is still very impressive. Furthermore, the Bank of Austria, in collaboration with the University of Vienna and several other organizations has successfully completed a quantum encrypted transaction just last month, and quantum encryption systems are beginning to go on the market, albeit for ridiculously high prices.

While this technology will not become commonplace anytime soon, and it is unlikely that it will ever become a household item, it is potentially very useful for large scale monetary transactions, spy agencies, top secret military communications, and especially ultra-paranoids, because lasers are definitely more fashionable than tin-foil hats.


Wikipedia ( "http://wikipedia.org/"): EPR paradox, Quantum Cryptography, Quantum Entanglement
Stanford Encycopedia of Philosophy ( "http://plato.stanford.edu/"): Quantum Entanglement and Infromation
NIST ( "http://www.nist.gov/public_affairs/releases/quantumkeys_background.htm"): Background on Quantum Key Distribution
TU Vienna QC ( "http://www.quantenkryptographie.at/"): Quantum Cryptography with Entangled Photons
Slashdot (slashdot.org)Search: Quantum Cryptography'
*I must admit that was a horrible joke, and it doesn't flow right at all, but I'm far too sleep deprived to remove it at this point

Log in or registerto write something here or to contact authors.