by Carolina Moura Alves, Adrian Kent

The central problem in cryptography is the key distribution problem, for which there are essentially two solutions: one based on Mathematics (public key cryptography) and one based on Physics (quantum cryptography). While public-key cryptography relies on the computational difficulty of factoring large integers, quantum cryptography relies on what we believe to be the universal laws of quantum mechanics. In fact, it has been shown that quantum computers can factor integers much faster than classical ones, so public-key cryptosystems are secure only as long as quantum computers are not built...

Quantum mechanics is the fundamental physical theory of matter. It has many counter-intuitive features, which are most easily observed on small sized physical systems (atoms, electrons, photons, etc.). Of these, the most relevant for cryptography are Heisenberg's uncertainty principle and quantum entanglement.

 

Uncertainty

 

knowing or measuring the value of one quantum observable (for instance, the position of a particle) implies an intrinsic uncertainty about the values of some other observables (for instance, its momentum). This means in particular that obtaining some information about an unknown quantum system generally causes a disturbance to the quantum state of that system. The security of quantum cryptography relies on this trade-off.

 

Entanglement

 

two spatially separated quantum systems that have interacted in the past may together share information in a form which cannot be accessed in any experiment performed on either of them alone. Some important quantum cryptography protocols exploit quantum entanglement, and it is crucial for long-distance quantum cryptography.

Using quantum mechanics for cryptography has its origins in the work of Stephen Wiesner, who, in the early 1970s wrote a paper titled "Conjugate Coding", in which he showed how quantum mechanics could be used to produce currency that could not be counterfeited. The ideas in the paper were later used by Charles Bennett and Gilles Brassard in 1984 to develop a quantum key distribution protocol, now known as the BB84 protocol. Subsequently, another novel quantum key distribution protocol was invented independently by Artur Ekert in 1991.

Based on these two counter-intuitive features of quantum mechanics (uncertainty and entanglement), two different types of quantum cryptographic protocols were invented. Both are based on the fact that quantum systems are disturbed by measurements performed on them. The first type uses the polarization of photons to encode the bits of information and relies on quantum randomness to keep Eve from learning the secret key. The second type uses entangled photon states to encode the bits and relies on the fact that the information defining the key only "comes into being" after measurements performed by Alice and Bob.

This cryptographic scheme uses pulses of polarized light, with one photon per pulse. Suppose the polarizations chosen for encoding the bits of information is the following: vertical polarization for "0" and horizontal polarization corresponds to "01001". In order to generate a random key, Alice must send either polarization with equal probability. To keep Eve from successfully eavesdropping, Alice also uses randomly the alternative linear diagonal polarizations: or encoding "0" or "1" respectively. The security of this scheme is based on the fact that Eve does not know whether any given pulse codes for 0 or 1 using the or the polarizations. If Eve tries to measure the state and guesses wrongly, she will disturb it, and Alice and Bob can monitor for such disturbances to test for possible eavesdropping and even estimate what fraction of the transmitted key Eve might have obtained. Bob does not know which polarizations were used for any given pulse coding either. (Alice could tell him, but since it has to be kept secret from Eve they would need a cryptographically secure communication channel to do this, and if they had one they wouldn't need this scheme.) However, he can guess, and half the time he will get it right. Once the photons are safely received, so that Eve cannot use the information, Alice can tell him which guesses were right and which wrong. for "1". Thus, the sequence of pulses

The Ekert scheme uses entangled pairs of photons. These can be made by Alice, by Bob, or by some source separate from both of them; in any case, they are distributed so that Alice and Bob each end up with one photon from each pair. The scheme relies on three properties of entanglement. First, we can make entangled states which are perfectly anti-correlated, in the sense that if Alice and Bob both test whether their particles have or polarizations, they will always get opposite answers, and the same is true if they both test whether they have or , or if they both carry out the same test for any other pair of complementary (orthogonal) polarizations. However, their individual results are completely random: it is impossible to predict in advance if Alice will get or .

Second, these states have a property often called quantum non-locality, which has no analogue in classical physics or everyday experience. If Alice and Bob carry out different polarization measurements, their answers will not be perfectly anti-correlated, or perfectly correlated, but they will in general be statistically correlated. That is, Alice can make a better than random guess at Bob's answer, given her own, and vice versa. And these correlations are stronger - in other words, Alice's guesses will on average be better - than any model based on classical physics or ordinary intuition would predict.

Third, any attempt at eavesdropping by Eve will weaken these correlations, in a way that Alice and Bob can detect.

Quantum cryptography protocols achieve something that ordinary classical cryptography cannot. They allow Alice and Bob to generate and share random keys which are very similar - in perfect conditions they would be identical, but actually there will be some error rate. They also allow Alice and Bob to estimate the level of eavesdropping and so work out the maximum amount of information Eve can have about their shared random keys. These are interesting results, but on their own they are not enough to solve the key distribution problem. It could be disastrous if Eve learns even a small part of the cryptographic key: she could then read part - perhaps a critical part - of the secret message Alice wants to send. Because errors and background noise can never completely be avoided, Alice and Bob can never guarantee that Eve has no information at all about their keys - communication errors and eavesdropping cannot be distinguished, and so to be on the safe side Alice and Bob have to assume that all discrepancies are due to Eve.

Happily (for Alice and Bob), while quantum cryptography was being developed, Ueli Maurer and other classical cryptographers were developing a technique called privacy amplification, which turns quantum cryptography into a practical technology for secure communications.

Privacy amplification is a sort of cryptographic version of error correction, which allows Alice and Bob to start with similar shared random keys about which Eve has some information and make shorter shared random keys which are identical and about which Eve has (essentially) no information.

Though classical privacy amplification can be used for either the Bennett-Brassard or the Ekert protocols, it turns out that entanglement-based cryptography allows privacy amplification to be carried out directly at the quantum level. This is more efficient, and has other advantages. In particular, when the technology is fully developed, it will allow quantum cryptography to be carried out over arbitrarily long distances by using quantum repeater stations along the communication route.

The problem of key distribution can also be solved through public-key cryptography. Read our mini tutorial on public-key cryptography