Quantum Cryptography

Introduction

Quantum cryptography is an attempt to allow two users to communicate using more secure methods than those guaranteed by traditional cryptography. Traditionally, cryptographic security relied on mathematics and took into account the limited computation powers that we have developed. Breaking a cryptographic code would involve factoring extremely large numbers into two primes, typically of over 100 digits in length, which was assumed to be impossible in a reasonable amount of time (less than a million years) even if all of the available computers today worked exclusively on one such problem. However, just because there is no algorithm efficient enough to do the factoring quickly, does not mean that such an algorithm could not be found eventually. Quantum cryptography, which uses photons and relies on the laws of quantum physics instead of "extremely large numbers," is the cutting edge discovery which seems to guarantee privacy even when assuming eavesdroppers with unlimited computing powers.

This page will explore the history of quantum cryptography, explain how quantum coding works and provide a detailed example. It will then analyze the level of privacy guaranteed by this technique, and talk about quantum cloning, which might eventually undermine the reliability of quantum cryptography. Finally, it will conclude with a discussion of the limitations and prospects of this technology in the modern world.

History (from 1970s to 2004)

Quantum cryptography was first proposed by Stephen Weisner in his work "Conjugate Coding" in the early 1970s. The proposal was published in 1983 in Sigact News, and by that time two scientists Bennet and Brassard, who were familiar with Weisner's ideas, were ready to publish their own ideas. In 1984, they produced the first quantum cryptography protocol, the "BB84." The first experimental prototype based on this was made in 1991. It operated over a distance of 32 centimeters. Over time, the technology has been refined and the distance increased to kilometers. (3, 6)

More recently, in June 2003, a team at the University of Vienna transmitted entangled photons across the river Danube, through free space. In April 2004, the first money transfer encrypted by quantum keys occurred between two Austrian banks. The two buildings were 500 meters apart, yet fibre optics were fed through 1.5 kilometers of sewage system to link them together. (5) Then on June 4th, 2004 the following excerpt was published in newscientist.com:

The first computer network in which communication is secured with quantum cryptography is up and running in Cambridge, Massachusetts. Chip Elliott, leader of the quantum engineering team at BBN Technologies in Cambridge, sent the first packets of data across the Quantum Net (Qnet) on Thursday. The project is funded by the Pentagon's Defense Advanced Research Projects Agency. Currently the network only consists of six servers, but they can be integrated with regular servers and clients on the internet. Qnet's creators say the implementation of more nodes in banks and credit card companies could make exchanging sensitive data over the internet more secure than it is with current cryptography systems. The data in Qnet flows through ordinary fibre optic cables and stretches the 10 kilometers from BBN to Harvard University... Qnet is the first network consisting of more than two nodes to use quantum cryptography - a more complex challenge [than the transfer of keys between two banks]... In Qnet, software-controlled optical switches made of lithium niobate crystals steer photons down the correct optical fibre. (2)

The process of quantum coding

Quantum cryptography is not replacing traditional cryptography; rather, it allows for a more secure transfer of the keys used in encoding and decoding. The amount of information which can be transferred using quantum cryptography is not very large or very fast, but it is very secure. The maximum speed, scale and security of the transfer is achieved by sending the secret key using quantum coding, but encoding and sending the data itself using traditional methods and algorithms. This way the users can ensure more privacy by making sure their key is as secure as modern technology can make it, while still transferring the information as quickly as possible.

Thus note than in the discussion that follows, "information exchange" refers just to the secret key, which is later used to decode the bulk of the information, not to the information itself. Many algorithms of encoding and decoding information using a given key have been created already, many years before quantum cryptography came into existence, and so they will not be discussed here.

Outline of the process

In quantum cryptography, data is converted to bits of 0s and 1s, and then transferred using polarized photons. Photons are put into a particular quantum state by the sender and are observed by the recipient. A photon can be in one of four polarizations: 90, 0, 45 and -45 degrees, and can be measured using three different bases: rectilinear (horizontal or vertical), circular (left-circular or right-circular), and diagonal. Only the rectilinear and circular bases are used here. The receiver can distinguish between a 0 and 90 degrees, or -45 and 45 degrees polarizations. Due to the physical principles, a measurement destroys the photon, so it is impossible to carry out both observations.

Thus the receiver not only needs to receive the signals, but also measure them with respect to the correct bases. This information can not be transferred between the sender and the receiver because, if intercepted, would allow a third party to obtain the secret key. Instead, the receiver randomly chooses one of the two: it either distinguishes between a 0 and 90, or -45 and 45 degree polarizations for each signal. Then the receiver contacts the sender, and publicly discusses which type of measurement was done for each bit. The sender confirms which types were correct, and the sender and the receiver both discards the bits that weren't measured accurately. This constitutes the key. (3, 4)

Accuracy and security

Now the two parties must make sure that their keys are the same, but do so in a way that wouldn't violate the security of the transfer. This is a crucial step because there might be errors introduced into the transfer by random noise or by eavesdroppers. To ensure the maximum accuracy without revealing the specific bits received, the sender and the receiver can discuss groups of bits instead of individual ones, and can compare the parity (the remainder when the sum is divided by 2) within those groups. This can even be done in public, as long as the individual bits remain secret. Groups with discrepancies in parity can then be discarded, or broken down into other groups (still ensuring that they are sufficiently large as to not reveal too much), one or more of which is discarded or corrected. In the end this process, if repeated enough times, guarantees that the keys are arbitrarily similar. (1, 7)

Furthermore, if after comparing their groups of bits this way, the sender and the receiver discard an agreed-upon bit, such as the last one, the parity revealed becomes useless to any eavesdroppers. Also, if desired, a publicly chosen hash function, h, can be used to map the string of received bits, x, into h(x), which can now be used as the key instead of x. It can be shown that by doing so, the eavesdropper's expected knowledge of h(x) can get arbitrarily small. (1)

Step-by-step example

A very nice online demonstration of the process of transferring information using quantum cryptography methods, created by Fred Henle, is located at http://monet.mercersburg.edu/henle/bb84/. The following is a specific step-by-step outline of the process, paraphrased and augmented from (3). Staying with the convention, Alice is used to refer to the sender, Bob to the receiver, and Eve to the eavesdropper in this description.

Sending

Alice determines the polarization (horizontal, vertical, left-circular or right-circular) of each burst of photons which she's going to send to Bob. Since a lot of this information will later be discarded, this can probably be done randomly. The goal is not to transfer a specific key, but to agree on a key that is common to both parties.
A light source from a light-emitting diode (LED) or from a laser is filtered to produce the desired polarized photons. Ideally, each pulse consists of a single photon. However, in real life it actually has to be a beam of light with very low intensity. If the intensity is too low, a pulse may be undetectable for the receiver, yet if it's too high, then the polarization of the photons can be detected discreetly (i.e. a photon from the beam can be measured by the eavesdropper with respect to both bases without any noticeable difference to the beam). Both cases are undesireable to say the least, so the intensity has to be regulated very carefully. (6)

Receiving and converting

Bob randomly generates a sequence of bases (rectilinear or circular), and measures the polarization of each photon with respect to one of them.
Bob tells Alice which sequence of bases he used, without worrying about other people hearing this information.
Alice publicly responds with which bases were chosen correctly.
Alice and Bob discard all observations except for those with the correctly-chosen bases.
The remaining observations are converted on to binary code (left-circular or horizontal is 0, and right-circular or vertical is 1).

Correcting errors - step 1

Alice and Bob agree on random permutations of bits in the resulting string, to randomize the positions of errors. Two errors next to each other are very hard to detect, yet it is likely that an error with the instruments or because of random noise would alter a sequence of bits one after the other. Randomization helps account for that.
The strings are partitioned into blocks of size k, with k ideally chosen to make the probability of multiple errors per block very small. Note that if Alice's string contains 101100 and Bob's contains 101111, the parity is the same, 1, even though there are two mistakes in the block. Making k small is one of the steps taken to minimize the chance of this happening, since the chances of having two errors in a block of size 50 is much less than in a block of 500, especially after the errors are randomized.
Alice and Bob compute and exchange parities for each block. This information can be made public, but, to ensure security, the last bit of each block is then discarded, making the information useless for Eve.
Any block with different reported is broken down further and a binary search is used to locate and correct the error. Alternatively, if the length of the key is already sufficiently large, those blocks could even be discarded.
Steps 9-12 are then repeated with increasing block size, k, in an attempt to discover multiple errors that could've gone undetected within original blocks.

Correcting errors - step 2

Finally, to determine if additional errors remain, Alice and Bob do another randomized check. They publicly agree on a random assortment of half the bit positions in their string, and compare parities, followed discarding the last digit, as always.
If the strings are different, then there is � probability of a disagreement of parities. Then a binary search is used to find and eliminate error, as described above.
After r repetitions of step 13 without disagreements, Alice and Bob can conclude that their strings disagree with probability (1/2)r, which can obviously be made arbitrarily small by increasing r.

Alternate methods of exchanging keys

Actually, the information can be exchanged in a number of ways, not just the one described above. Below is a brief description of two of those. (6)

One-time pad method

Alice generates two random bits, B1 and B2. She uses B1 to select the basis and B2 to select the polarization of the photon. Bob generates a random bit B3 and sets his detector to that basis. He then reads Alice's signal using that basis, and records B4.
Alice and Bob compare B1 and B3, the bases they used, over a public channel. These bases will be the same half of the time, since Alice's base can be one of two things, and so can Bob's, so out of the four possibilities, namely (B1, B3) = (0, 0), (0, 1), (1, 0), (1, 1), two match.
If B1 and B3 don't match, then the bit needs to be resent until they do match. Note that each time the bases should be chosen randomly, to ensure privacy.
When B1 and B3 match, Alice and Bob record B2 and B4, knowing that they are the same unless Eve is listening, in which case she would be changing the states of the photons. Later comparing the strings using binary search as described in the previous section would allow Alice and Bob to detect any such interventions.

Quantum entanglement

This process uses entangled photons, which can be generated by firing a laser through a crystal and splitting a single photon into two. The most interesting thing about them is that, by the laws of physics, disturbing the state of one will instantly disturb the other, no matter how far apart they are. This is extremely useful in detecting eavesdroppers, as will be discussed below.

The technicalities of such a transfer are similar to the original process described, where Alice sends polarized photons to Bob, who measures them using randomly selected states. However, here a photon generator is placed between Alice and Bob so that pairs of entangled photons with the same polarization go to Alice and Bob at the same time. Then both parties measure the signals with randomly varying bases, and record the result and the time received. After comparing the bases, they can discard the bits measured with different bases, and keep those that are the same. They can then test for errors using the algorithms described above. Note that while this method is very similar to the original one described, they are different in terms of security and detection of intervention, as described below.

Privacy measures

It is clear that transfers using quantum cryptography are much more secure than those that use traditional cryptography, because quantum methods rely on the laws of physics instead of the impracticality of calculating certain mathematical problems. Given the algorithms that exist today, those problems would required thousands of years to solve, but it is still not an impossible, and no one has proven that there does not exist and efficient algorithm which yields the result sooner, perhaps even in a matter of hours or minutes.

Quantum mechanics provides a way of transferring secret keys over extremely secure channels. After the keys are exchanged, there is very little concern that someone would be able to decode the data without these keys, since they are different every time and are always generated randomly, or at least become random after about half the bits are discarded to match the polarization states measured by Alice and Bob, and after the error-correcting algorithms. So the only real concern in the system is ensuring that Eve does not intercept the secret key during transfer, which is unlikely.

What makes quantum cryptography so secure is the fact that it's easy to detect eavesdroppers and correct the damage they cause. So the two parties are always aware if their channel is not very secure, assuming they take all the necessary percussions. However, due to some practical imperfections of this theoretically perfect system, as well as to the constant improvement of technology, there might still be some small loopholes.

Detecting eavesdropping

The key here is that it is impossible to measure the polarization of the photon without destroying it. So if Eve intercepts the signal and measures the photons, she will have to send new photons onto the receiver if she doesn't want to be detected. However, she will inevitably introduce errors, since she doesn't know which state to measure in, and so in which polarization to send them in. So Alice and Bob can simply check for errors by revealing a random subset of their generated sequence and comparing it publicly. If they are not satisfied with the error rate, they can try to set up a different channel. This ensures that while Alice and Bob can not stop Eve from listening in, they would always know that she is there.

A similar method can be used with entangled photon transfer. By the laws of physics, a change in the polarization of one photon in the pair will affect the other one, no matter how far apart they are. In order to eavesdrop, Eve would have to detect one of the photons and measure it, thus destroying half of the pair. This act will end the quantum relationship of the two members of the pair, which is very easy to detect by Alice and Bob, and impossible to reverse for Eve. Without revealing the specific results of their measurements, the sender and the receiver can talk publicly and see where intervention has taken place. (4)

Possible loopholes

The practical implementation of quantum cryptography is not perfect. For one, it is impossible to use single photons to transmit information, so small bursts of light are used instead. So it could be possible for Eve to isolate single photons from the beam and measure them, only reducing the intensity of the light slightly. This would be virtually impossible to detect, because this reduction could be attributed to the fact that light had to travel over a long distance, and there are possible imperfections in the channel.

These imperfections, or noise, are a big problem in detecting eavesdropping. Intervention by a third party and noise produce identical results as far as Alice and Bob are concerned, so since noise can never be entirely avoided in the physical world, they might have to sacrifice some of their privacy and hope that the interference they are getting is not coming from Eve. This might make eavesdropping without detection possible, as long as the attacker is operating very slowly and carefully; however, various methods have been suggested that could deal with this problem. (3)

Quantum cloning

The techniques of quantum cryptography provide no protection against the so-called "bucket brigade," or "man-in-the-middle," attack, where the eavesdropper can intercept, receive, copy, and resend messages with perfect accuracy and without delay. However, it is believed that the laws of physics will prohibit such an eavesdropper from ever occurring. Nevertheless, while entangled photons are still considered absolutely safe, a group of Oxford researchers led by Antia Lama-Linares considered the possibility of eavesdropping on regular photon transfer, and were able to achieve amazing results.

In 1997, they started wondering how well they can copy a quantum state, or the polarization of the photon, and thus produce a "quantum clone." The theoretical accuracy limit of copying the clone is 5/6, or 83%. The group reported that they copied the quantum state with 81% accuracy. They used the process of stimulated emission, and sent the photon into a crystal with atomic states that have been excited by laser pulses. So when the photons entered, its presence stimulated the emission of the clone photon, which was in the same identical state. The only problem was that the crystal also spontaneously emitted light, which is the noise that prevented the theoretical accuracy from ever achieving 100%. (1)

Potential dangers

There are two possible ways of viewing this result. One, presented by Richard Hughes of the Los Alamos National Laboratory in the US, is that this does not make quantum cryptography more susceptible to eavesdroppers. First, copying a transmission with 83% accuracy is not even close to decoding 5 out of 6 letters in the message. Second, there are various mathematical algorithms which were developed long before quantum cryptography, that allow the users to amplify the privacy of their exchanges even when communicating along non-secure channels. So as long as users are careful and assume the presence of eavesdroppers, they can amplify their privacy beyond Eve's ability to decode.

A different view, however, was presented by Hoi-Kwong Lo from the quantum computing and cryptography firm Magiq Technologies. He is worried that there are many possible technology developments in the near future and many loopholes in the system which are not obvious to anybody today, but may well be discovered tomorrow. Theoretical safety against eavesdroppers is not enough, and mathematical tricks can not fully compensate for the possible danger of cloning. All that matters is the physical safety of the information, which is obviously threatened by the ability to clone photons, which was thought to be impossible earlier. (1)

Prospects

Clearly, quantum cryptography is still a long way from being common in information transfer, because the real world is still a long way from theoretical perfection. However, it's important to keep in mind that the basic foundation for this great technique has been laid, and so now it only needs to be refined.

Current limitations

For now, computers capable to transmitting information using quantum cryptography are very large, custom-made and, thus, expensive. A couple of banks have already taken advantage of this security method, but few other organizations would be able to afford it in the foreseeable future.

With regards to entangled photons, which seem to be absolutely safe, there is also a serious practical problem not only with the cost, but also with keeping them entangled long enough to meet the needs of the real world. While the system is perfect in theory, it is going to be very hard to implement it in practice.

Another problem is that for distances beyond 50 kilometers or so, the noise becomes so great that error rates skyrocket. This not only leaves the channel very vulnerable for eavesdroppers, but also makes it virtually impossible to send information. However, it is potentially possible for quantum keys to be exchanged through the air in the future. Tiny telescopes would then have to be aligned to detect the signal. Some calculations even suggest that photons could be detected by a satellite, which would allow communication between continents!

The future of quantum cryptography

For now, non-quantum cryptography is still very safe, because it relies on algorithms that can't be cracked in less than the lifetime of the universe by all the currently existing computers. So in theory, there is not much need for quantum cryptography yet; however, we never know when technology will take a leap forward and quantum techniques will become necessary to protect our information. When quantum computers will come into play, the computational speeds will increase dramatically, so the mathematical complexity of algorithms will become less of a challenge. It is still debatable whether or not it will be possible to simply increase the numbers use in the algorithms and thus increase the complexity enough to outrun even quantum computer.

Yet there is no debate about the fact that quantum cryptography is a true breakthrough in the field. It is still being refined and developed further. However, already it is clear that even with its current imperfections, it is many steps above everything that was developed before it. All we need is some years, or maybe decades or even centuries, to refine the technique and make it practical in the real world.

Modern Cryptography: Theory and Applications