Jump to content

Quantum key distribution

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 62.254.128.6 (talk) at 23:12, 31 May 2005 (→Four state protocol). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Quantum cryptography is an approach to securing communications based on certain phenomena of quantum physics. Unlike traditional cryptography, which employs various mathematical techniques to restrict eavesdroppers from learning the contents of encrypted messages, quantum cryptography is focused on the physics of information. The process of sending and storing information is always carried out by physical means, for example photons in optical fibres or electrons in electric current. Eavesdropping can be viewed as measurements on a physical object---in this case the carrier of the information. What the eavesdropper can measure, and how, depends exclusively on the laws of physics. Using quantum phenomena such as quantum superpositions or quantum entanglement one can design and implement a communication system which can always detect eavesdropping. This is because measurements on the quantum carrier of information disturb it and so leave traces.

Some commercially-available products have appeared based on quantum cryptography, for example, ID Quantique or MagiQ.

Quantum key exchange

A central problem in cryptography is the key distribution problem. One solution is based on mathematics, public key cryptography. Another approach is based on physics: quantum cryptography. While public-key cryptography relies on the computational difficulty of certain hard mathematical problems (such as integer factorisation), quantum cryptography relies on the laws of quantum mechanics.

Quantum theory is believed to govern all objects, large and small, but its consequences are most conspicuous in microscopic systems such as individual photons, atoms and molecules. Quantum cryptographic devices typically employ individual photons of light and take advantage of either the Heisenberg uncertainty principle or quantum entanglement.

Uncertainty: The act of measurement is an integral part of quantum mechanics, not just a passive, external process as in classical physics. So it is possible to encode information into some quantum properties of a photon in such a way that any effort to monitor them necessarily disturbs them in some detectable way. The effect arises because in quantum theory, certain pairs of physical properties are complementary in the sense that measuring one property necessarily disturbs the other. This statement is known as the Heisenberg uncertainty principle. It does not refer merely to the limitations of a particular measurement technology: it holds for all possible measurements. The two complementary properties that are often used in quantum cryptography, are two types of photon’s polarization, e.g. rectilinear (vertical and horizontal) and diagonal (at 45 or 135 degrees).

Entanglement: It is a state of two or more quantum particles, e.g. photons, in which many of their physical properties are strongly correlated. The entangled particles cannot be described by specifying the states of individual particles and they may together share information in a form which cannot be accessed in any experiment performed on either of the particles alone. This happens no matter how far apart the particles may be at the time. Entanglement is crucial for long-distance quantum key distribution.

Two different approaches

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.

Four state protocol

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 for "1". Thus, the sequence of pulses 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.


Alice wants to send a message to Bob. They both have devices that can generate polarised pulses of light, and also devices that detect the polarization of light. The polarization of the light will be used to represent the bits of data. For example, if the polarisation scheme or "basis" is up/down or left/right then up/down could represent 1 and left/right 0. The polarisation scheme can also be changed, so that as well as up/down and left/right, there could be any number of pairs of polarisations; for example top-left/bottom-right = 1 and top-right/bottom-left = 0.

First they must deal with errors, which may be introduced by random noise or by eavesdroppers, but must be discussed in general, so as not to compromise the information. This may be accomplished by discussing parities rather than individual bits; by discarding an agreed-upon bit, such as the last one, the parity can then be made useless to eavesdroppers.

Once the secret bit string is agreed to, the technique of privacy amplification can be used to reduce an outsider's knowledge of it to an arbitrarily low level. If an eavesdropper knows ℓ "deterministic bits" (e.g., bits of the string, or parity bits) of the length n string x, then a randomly and publicly chosen hash function h can be used to map the string x onto a new string h(x) of length n − ℓ − s for any selected positive s. It can then be shown that the eavesdropper's expected knowledge of h(x) is less than 2−s/ln 2 bits.

The actual information exchange can occur in a number of forms. The first is by generating a one-time pad as follows:

  1. Alice generates two random bits B1 and B2 and sends a pulse of light. B1 selects the basis and B2 the polarization within that basis.
  2. Bob generates a random bit B3 and sets his polarization detector to that basis. He reads bit B4.
  3. Bob and Alice tell each other B3 and B1 over a public, but authenticated, channel. If they agree, they add B2 and B4 to their pads, knowing that they are the same unless Eve is listening (Eve doesn't know B1 at the time of Alice's pulse transmission).

To send a message:

  1. Alice takes a message bit and two pad bits. She uses one pad bit to set the basis, XORs the other with the message, and uses it to select the polarization. She sends a light pulse.
  2. Bob takes the two pad bits, sets the basis according to the first, receives the light pulse, and XORs it with the second to get the data bit.

Another method of generating bits for the pad involves quantum entanglement. A photon generator is placed midway between Alice and Bob in such a way that pairs of photons with the same polarization go to Alice and Bob at the same time. Alice and Bob rapidly vary the basis of their polarization detectors and record the results and times. They tell each other the time and basis of each photon they detected and keep the ones that are the same. The bits are determined from the polarizations.

A different method of exchange is: Alice transmits pulses to Bob. Bob tells Alice publicly what sequence of bases were used. Alice tells Bob publicly which bases were correctly chosen. Alice and Bob discard all observations not from these correctly-chosen bases. The observations are interpreted using a binary scheme: for instance, left-circular (or horizontal) is 0, and right-circular (or vertical) is 1. This protocol is complicated by the presence of noise, which may occur randomly or may be introduced by eavesdropping.

When noise exists, polarizations observed by the receiver may not correspond to those emitted by the sender. In order to deal with this possibility, Alice and Bob must ensure that they possess the same string of bits, removing all discrepancies. This is generally done using a binary search with parity checks to isolate differences; by discarding the last bit with each check, the public discussion of the parity should betray no useful information. This works by Alice and Bob agreeing on a random permutation of bit positions in their strings (to randomize the location of errors). The strings are partitioned into blocks of size k (k being chosen, ideally, so that the probability of multiple errors per block is small). For each block, Alice and Bob compute and publicly announce parities. The last bit of each block is then discarded. For each block for which their calculated parities are different, Alice and Bob use a binary search with log(k) iterations to locate and correct the error in the block. To account for multiple errors that might remain undetected, steps 1-4 are repeated with increasing block sizes in an attempt to eliminate these errors.

To determine whether additional errors remain, Alice and Bob repeat a randomized check: Alice and Bob agree publicly on a random assortment of half the bit positions in their bit strings. Alice and Bob publicly compare parities (and discard a bit). If the strings differ, the parities will disagree with probability 1/2. If there is disagreement, Alice and Bob use a binary search to find and eliminate it, as above. If there is no disagreement after ℓ iterations, Alice and Bob conclude their strings agree with low probability of error (2−ℓ).

Attacks

In Quantum Cryptography, the traditional man-in-the-middle attack attack proves to be impossible due to Heisenberg's uncertainty principle. If Mallory attempts to intercept the stream of photons, he will inevitably alter them if he uses an incorrect detector. He cannot re-emit the photons to Bob correctly, which will introduce unacceptable levels of error into the communication.

If Alice and Bob are using an entangled photon system, then it is virtually impossible to hijack these, because creating three entangled photons would decrease the strength of each photon to such a degree that it would be easily detected. Mallory cannot use a man-in-the-middle attack, since he would have to measure an entangled photon and disrupt the other photon, then he would have to re-emit both photons. This is impossible to do, by the laws of quantum physics.

Other attacks are possible. Because a dedicated fiber optic line is required between the two points linked by quantum cryptography, a denial of service attack can be mounted by simply cutting the line or, perhaps more surreptitiously, by attempting to tap it. If the equipment used in quantum cryptography can be tampered with, it could be made to generate keys that were not secure using a random number generator attack.

History

Quantum cryptography was discovered independently in the US and Europe. The first one to propose it was Stephen Wiesner, then at Columbia University in New York, who, in the early 1970's, introduced the concept of quantum conjugate coding. His seminal paper titled "Conjugate Coding" was rejected by IEEE Information Theory but was eventually published in 1983 in SIGACT News (15:1 pp. 78-88, 1983). In this paper he showed how to store or transmit two messages by encoding them in two “conjugate observables”, such as linear and circular polarization of light, so that either, but not both, of which may be received and decoded. He illustrated his idea with a design of unforgeable bank notes. A decade later, building upon this work, Charles H. Bennett, of the IBM T.J. Watson Research Center, and Gilles Brassard, of the Université de Montréal, proposed a method for secure communication based on Wiesner’s “conjugate observables”. In 1990, independently and initially unaware of the earlier work, Artur Ekert, then a Ph.D. student at the University of Oxford, developed a different approach to quantum cryptography based on peculiar quantum correlations known as quantum entanglement. Since then quantum cryptography has evolved into a thriving experimental area and is quickly becoming a commercial proposition.

Prospects

Because entangled quantum states are, in the real world, rarely usefully stable, there is a serious practical problem in keeping them entangled long enough to meet the needs of real world interaction between correspondents or real world cryptanalytic use. The first commercial applications of quantum cryptography have thus a limited reach (100 kilometers maximum). Research is done into satellite transmission of the quantum states, since outside the atmosphere, there would be considerably less perturbating interactions.

Commercial quantum cryptography devices are on the market from a few vendors, and this technique shows promise of replacing such protocols as Diffie-Hellman key exchange in some high value applications. Factors weighing against its wide application include the cost of the needed equipment and dedicated fiber optic line, the requirement to trust the equipment vendor (as contrasted with open source encryption software running on off the shelf computers), and the lack of a demonstrated threat to existing key exchange protocols. It is also worth noting that the wide availibility of inexpensive mass storage makes it easier to send large quantities of keying material by courier. For example, some quantum cryptography vendors offer systems that change AES keys 100 times a second. A year's supply of AES128 keys, changed at that rate, will fit on a high-end iPod.

See also

References

Retrieved from "https://en.wikipedia.org/w/index.php?title=Quantum_key_distribution&oldid=14507617"