Quantum cryptography

 

Introduction, history, and basic idea

The most sophisticated cryptosystems in recent history have relied on mathematics and computational analysis to provide relative security.

Quantum cryptography is different from traditional cryptography in that we are taking advantage of the properties of matter in addition to the principles of mathematics to create a cryptosystem that cannot be broken with unlimited computing power (even with a quantum computer).

Although current cryptosystems would be compromised by functional quantum computers, quantum mechanics offers alternative cryptosystems that could not be broken even by a quantum computer. In 1970, Stephen J. Wiesner in [10] used the laws of quantum mechanics to design a theoretical bank note that would be impossible to duplicate, and he also described a way that two messages could be combined into one message where only one of the messages could be read while the other would be destroyed. Wiesner's discovers were little noticed at the time, but they would lead to the first quantum cryptosystems.

In the early 1980's, Bennett and Brassard took the ideas of Wiesner and employed them in a new cryptosystem design. After modifications, this cryptosystem is now considered to be possibly unbreakable. In classical cryptosystems, we have always assumed that Eve can passively observe transmissions over a non-secure channel. This turns out not to be true in the quantum world because observation is tightly connected with the observed phenomenon, and this fact will lead to quantum cryptography.

Certain pairs of properties in quantum mechanics are such that measuring one will necessarily affect the other. One such pair of properties is the rectilinear and diagonal polarization of light. The polarization of a light wave can be in any direction. The direction of the light polarization can be made to be a specific angle by passing light through a polarizing filter (see figure 1).

figure 1: polarization of light into vertically polarized light; vertical light passed through a diagonal polarizing filter can come out either vertical or could be blocked.

The polarization of the light can also be measured using a polarizing filter. If we use a vertical polarizing filter, then vertically polarized light will pass through while horizontally polarized light will not pass through. We can tell whether the light was vertical or horizontal by seeing whether it passed through or not. However, if the light is at a 45 or 135 degree angle, the light might or might not pass through, and if it does pass through then it will be vertical. We cannot conclude from the observation whether the light was at a 45 or 135 degree angle. This property of light leads to the quantum cryptosystem described below.

 

The quantum cryptosystem

1. Alice prepares a series of photons with random polariziations - either 45, 90, 135, or 180 degrees. She sends these photons to Bob over a quantum channel.

2. Bob measures the photons. He must choose whether to measure them using a rectilinear or diagonal polarizing filter. He randomly uses either one and keeps a record of which one he used for which bit. If he measures either 45 or 90 degrees, he records a 0, and if he measures either 135 or 180 degrees he records a 1.

3. Over a normal insecure channel, Alice and Bob communicate and figure out which bits Bob used the correct polarizing filter for. These values are now a secret to Alice and Bob.

4. Finally, Alice and Bob perform error correcting and check to see if Eve was listening. Described below.

figure 2: the quantum cryptosystem with both a normal channel and a quantum channel.

 

Possible attacks on the quantum cryptosystem

Eve at first believes that she can simply observe the photons as they go by and note what their values are. Let us assume that Alice sends a photon that is 90 degrees. Eve randomly guesses to use a diagonal polarizing filter to measure the polarization. Because she is using the wrong filter, the value she measures could be either 45 or 135. Let us assume that she measures 135 degrees. She records a 1 and then sends this value along to Bob. Bob then measures the photon using a rectilinear polarizing filter and could observe either a 1 or a 0. When Bob and Alice communicate which bits he used the correct polarizing filter for, this bit will be among that set. However, Bob will have received the wrong bit because of Eve's interference. In the 4th step, Alice and Bob check to see if anyone was listening. Because Eve's interference will cause Bob to observe some of the bits incorrectly, Alice and Bob compare a small portion of the secret key obtained in step 3. If there is a high enough error rate, Bob and Alice know that someone was listening, and they start the whole process over again. Eve could not simply observe the photons going by and know what the secret key is.

However, Eve could thwart communication of the secret key by continually observing the photons. Alice and Bob would have to keep starting the process over and over again, and they would never be able to establish their secret key. Although they would not be able to establish their secret key, they would know that there is interference and might be able to take appropriate actions.

Another possible attack that Eve can use is to split off a certain portion of the beam of light going by while leaving the rest in tact. This attack is possible if Alice sends a stream of light for each bit that all has the same polarization. If Eve were to split off a small portion, the decrease in brightness may go unnoticed. Alice can prevent this attack by trying to send only a single photon at a time. The polarization of this photon cannot be duplicated because of the uncertainty principle. [1] references recent experiments that have been successful at producing one photon at a time.

Eve could also attempt to listen to only a small number of bits going by in hopes that she can know a few bits and go undetected. Alice and Bob can prevent this attack by shrinking their secret key down after having established it. If they shrink their key in the right way, Eve's chances of knowing even one bit would be very small.

One attack that the system is vulnerable to is impersonation. The system assumes that Eve is not able to impersonate either Alice or Bob on the normal or quantum channel. [7] claims that there are ways to get around this with error correcting codes or with an unjammable channel. [7] also claims that it has been proven that this cryptosystem cannot be broken by analyzing the data using even a quantum computer. It has not been proven that the system is invulnerable to more sophisticated attacks taking advantage of the physics of the system. These attacks would have to be very sophisticated, and it is possible that they will be proven impossible in the future.

 

Conclusion

The cryptosystem we have been discussing in this paper is only useful for communication between individuals. [7] discusses a possible cryptosystem taking advantage of quantum phenomenon that could be used to store data securely for long periods of time. This cryptosystem would be unbreakable but is very impractical with current technology (the data could only be stored for a fraction of a second).

We have seen that the quantum cryptosystem is a way of exchanging a secret key without ever having met in person or having access to a secure channel. This secret key could then be used for a one time pad cipher. Used in this way, quantum cryptography is likely unbreakable. A fully functional prototype of the system was built in 1989 at IBM that had a separation of 32 cm in between Alice and Bob. This prototype proved that the system does work practically as well as in theory. There have been other recent breakthroughs in technology that indicate that quantum cryptography will be practical before quantum computers.

If quantum cryptography is proven unbreakable and becomes practical, then the code makers will have won the battle against the code breakers.

 

References

1. Benjamin, Simon, "Single Photons 'on Demand'", Science vol. 290, 2000, pp. 2273-2274.

2. Bennett, Charles H. and Shor, Peter W., "Privacy in a Quantum World", Science vol. 284, 1999, pp. 747-748.

3. Bennett, C. H., Bessette, F., Brassard, G., Salvail, L. and Smolin, J., "Experimental quantum cryptography", Journal of Cryptology, vol. 5, no. 1, 1992, pp. 3 - 28

4. Brassard, G., Crépeau, C., Jozsa, R. and Langlois, D., "A quantum bit commitment scheme provably unbreakable by both parties", Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, November 1993, pp. 362 - 371.

5. Brassard, Gilles, "A bibliography of quantum cryptography", http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC.html, April 24, 2002.

6. Bennett, C. H., "Quantum cryptography: Uncertainty in the service of privacy", Science, vol. 257, 7 August 1992, pp. 752 - 753.

7. Bennett, C. H., Brassard, G. and Ekert, A. K., "Quantum cryptography", Scientific American, October 1992, pp. 50 - 57.

8. Ekert, A. K., "Quantum cryptography based on Bell's theorem", Physical Review Letters, vol. 67, no. 6, 5 August 1991, pp. 661 - 663.

9. Shor, P.W., "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM J. Computing 26, pages 1484-1509 (1997).

10. Werner, M. J. and Milburn, G. J., "Eavesdropping using quantum-nondemolition measurements", Physical Review A, vol. 47, no. 1, January 1993, pp. 639 - 641.

11. Wiesner, S., "Conjugate coding", Sigact News, vol. 15, no. 1, 1983, pp. 78 - 88; original manuscript written circa 1970.