Quantum cryptography
From Wikipedia, the free encyclopedia
Quantum cryptography uses quantum mechanics for secure communications. Unlike traditional cryptography, which depends on the computational complexity of mathematical techniques to restrict the possibility that eavesdroppers might learn the contents of encrypted messages, quantum cryptography depends on the fact that naive attempts to read quantum information will destroy the information (ie. there is no way to copy unknown quantum states). For the message participants, a combination of quantum and classical techniques is used to produce a key which can be proven to be secure —that is, a produced hidden key cannot have been read by any other than the intended participants.
In quantum information, eavesdropping can be viewed as measurements on a physical object — in this case the carrier of the information. 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 disturbs it and therefore leaves traces.
Contents |
[edit] Quantum key exchange
Whereas classical public-key cryptography relies on the computational difficulty of certain hard mathematical problems (such as integer factorization) for key distribution, quantum cryptography relies on the laws of quantum mechanics. Quantum cryptographic devices typically employ individual photons of light and take advantage of either the Heisenberg uncertainty principle or quantum entanglement.
Uncertainty: Unlike in classical physics, the act of measurement is an integral part of quantum mechanics. So it is possible to encode information into quantum properties of a photon in such a way that any effort to monitor them 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. 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° and 135°).
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.
[edit] 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. 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.
[edit] Polarized photons - Charles H. Bennett and Gilles Brassard (1984)
This cryptographic scheme, known as BB84, uses pulses of polarized light, with one photon per pulse. Consider two types of polarization, linear and circular. Linear polarization can be vertical or horizontal and circular polarization can be left-handed or right-handed. Any type of polarization of a single photon can encode one bit of information, for example, vertical polarization for "0" and horizontal polarization for "1" or left-handed polarization for "0" and right-handed polarization for "1". In order to generate a random key, Alice must send either horizontal or vertical polarization with equal probability. To keep Eve from successfully eavesdropping, Alice also randomly uses the alternative circular polarizations, arbitrarily choosing between left-handed and right-handed photons.
[edit] Entangled photons - Artur Ekert (1991)
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, including eavesdropper Eve, although the problem of certifying them will arise. In any case, the photons 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 correlated in the sense that if Alice and Bob both test whether their particles have vertical or horizontal polarizations, they will always get opposite answers. The same is true if they both measure any other pair of complementary (orthogonal) polarizations. However, their individual results are completely random: it is impossible for Alice to predict if she will get vertical polarization or horizontal polarization.
Second, these states have a property often called quantum non-locality, which has no analogue in classical physics. If Alice and Bob carry out polarization measurements, their answers will not be perfectly correlated, but they will be somewhat correlated. That is, there is an above-50% probability that Alice can, from her measurement, correctly deduce Bob's measurement, and vice versa. And these correlations are stronger - 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.
[edit] Privacy amplification
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.
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.
[edit] Limitation: no deniability
One limitation of quantum key exchange via Bennett and Brassards approach is that although it may be used to create one time pad keys providing 'perfect security', it may affect the one time pad's deniability property ie. that the sender (Alice) may encrypt a message with one key, but after having sent the encryption pretend that the message was a different one, encrypted with a different key.
The reason for this is that an eavesdropper (Eve) who only listens to a very small part of the key exchange (and therefore disturbs a few bits, but not enough to invalidate the protocol) will then know what has happened in a limited number of the bits exchanged. If challenged to reveal what was sent and the key used, Alice and Bob must change the key, and therefore must alter their records which were used to obtain it, in order to 'deny' the message. However, there is a non-zero probability that Eve has successfully listened to the parts of their records that they change. She will therefore know that the key they are pretending to have used is false, and therefore that they are lying.
This problem is related to in the impossibility of 'bit commitment' using quantum protocols.
It is thought that other protocols using elliptic curves, and quantum computers may allow deniability to be reascribed to QKE.
(See D Beaver On Deniability in QKE. EUROCRYPT conference 2002)
[edit] Attacks
In Quantum Cryptography, traditional man-in-the-middle attacks are impossible due to the Observer Effect. If Mallory attempts to intercept the stream of photons, he will inevitably alter them. He cannot re-emit the photons to Bob correctly, since his measurement has destroyed information about the photon's full state and correlations.
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.
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.
Quantum cryptography is still vulnerable to a type of MITM where the interceptor (Eve) establishes herself as "Alice" to Bob, and as "Bob" to Alice. Then, Eve simply has to perform QC negotiations on both sides simultaneously, obtaining two different keys. Alice-side key is used to decrypt the incoming message, which is reencrypted using the Bob-side key. This attack fails if both sides can verify each other's identity.
Adi Shamir has proposed an attack which applies at least to polarization schemes. Rather than attempt to read Alice and Bob's single photons, Mallory sends a large pulse of light back to Alice in between transmitted photons. Alice's equipment inevitably reflects some of Mallory's light. Even if the transmitting equipment is dead black it has some small reflectivity. When Mallory's light comes back to Mallory it is polarized and Mallory knows the state of Alice's polarizer.
[edit] History
Quantum cryptography was proposed first by Stephen Wiesner, then at Columbia University in New York, who, in the early 1970s, 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 Thomas 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.
[edit] Prospects
As of March 2007 the longest distance over which quantum key distribution has been demonstrated using optic fibre is 148.7 km, achieved by Los Alamos/NIST using the BB84 protocol[1]. Significantly, this distance is long enough for almost all the spans found in today's fibre networks. The distance record for free space QKD is 144km, achieved by a European collaboration using entangled photons (Ekert scheme)[2]. This suggests transmission to satellites is possible, due to the lower atmospheric density at higher altitudes. For example although the minimum distance from the International Space Station to the Optical Ground Station telescope is about 400 km, the atmospheric thickness is about an order of magnitude less than in the European experiment, thus yielding less attenuation compared to this experiment.
There are currently three companies offering commercial quantum cryptography systems; id Quantique (Geneva), MagiQ Technologies (New York) and SmartQuantum (Brittany). Several other companies also have active research programmes, including Toshiba, HP, IBM, Mitsubishi, NEC and NTT.
The current commercial systems are aimed mainly at governments and corporations with high security requirements. Key distribution by courier is typically used in such cases, where traditional key distribution schemes are not believed to offer enough guarantee. This has the advantage of not being intrinsically distance limited, and despite long travel times the transfer rate can be high due to the availability of large capacity portable storage devices. The major difference of quantum cryptography is the ability to detect any interception of the key, whereas with courier the key security cannot be proven or tested. QKD systems also have the advantage of being automatic, with greater reliability and lower operating costs than a secure human courier network.
Factors preventing wide adoption of quantum cryptography outside high security areas include the cost of equipment, and the lack of a demonstrated threat to existing key exchange protocols. However, with optic fibre networks already present in many countries the infrastructure is in place for a more widespread use.
[edit] See also
- Secure Communication based on Quantum Cryptography (SECOQC)
- Trojan horse (computing)
- Clone (computer science)
[edit] External links
- Quantum Cryptography Mailing List
- European portal of Quantum Cryptography
- Elementary explanation of quantum entanglement and quantum cryptography
- Quantum Cryptography with Entangled Photons
- MetroWest Daily News A quantum leap: Researchers create super-secure computer network
- The BB84 Protocol for Quantum Cryptography [1]
- Error Detection and Correction in Quantum Cryptography (Cascade) [2]
- Three-stage quantum cryptography [3]
- Early article on experimental quantum cryptography [4]
- Entanglement-based quantum cryptography [5]
- The Register: Quantum crypto comes to Blighty
- D. Stucki, N. Gisin, O. Guinnard, G. Ribordy, H. Zbinden. Quantum Key Distribution over 67 km with a plug & play system
- Scientific American Magazine (January 2005 Issue) Best-Kept Secrets
- A Quantum Cryptography Computer Simulator Fernando Lucas Rodriguez
- Slashdot interviews Schneier about quantum cryptography
- Hold the Photons! and "Totally Secure Classical Communications?" by Schneier describe an algorithm very similar to quantum cryptography, but using much cheaper classical components.
- "Application of Genetic Algorithms to Recovering Corrupted File Streams" by Phillips attempts to defeat using assumption of text encoding in ASCII
Companies selling quantum devices for cryptography
- SmartQuantum SmartQuantum Industrial quantum cryptographic solution
- id Quantique SA sells Quantum Key Distribution products
- MagiQ Technologies sells quantum devices for cryptography
Companies with quantum cryptography research programmes
[edit] References
- ^ http://www.iop.org/EJ/article/1367-2630/8/9/193/njp6_9_193.html
- ^ http://lanl.arxiv.org/abs/quant-ph/0607182
| Quantum computing |
|---|
| Qubit | Quantum circuit | Quantum computer | Quantum cryptography | Quantum information | Quantum programming | Quantum teleportation | Quantum virtual machine | Timeline of quantum computing |
| Quantum algorithms |
| Deutsch-Jozsa algorithm | Grover's search | Shor's factorization |
| Nuclear magnetic resonance (NMR) quantum computing |
| Liquid-state NMR QC | Solid-state NMR QC |
| Photonic computing |
| Nonlinear optics | Linear optics QC | Non-linear optics QC | Coherent state based QC |
| Trapped ion quantum computer |
| NIST-type ion-trap QC | Austria-type ion-trap QC |
| Semiconductor-based quantum computing |
| Kane QC | Loss-DiVincenzo QC |
| Superconducting quantum computing |
| Charge qubit | Flux qubit | Hybrid qubits |
