Quantum key distribution

Quantum cryptography, or quantum key distribution (QKD), uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random bit string known only to them, which can be used as a key to encrypt and decrypt messages.

An important and unique property of quantum cryptography is the ability of the two communicating users to detect the presence of any third party trying to gain knowledge of the key. This results from a fundamental part of quantum mechanics: the process of measuring a quantum system in general disturbs the system. A third party trying to eavesdrop on the key must in some way measure it, thus introducing detectable anomalies. By using quantum superpositions or quantum entanglement and transmitting information in quantum states, a communication system can be implemented which detects eavesdropping. If the level of eavesdropping is below a certain threshold a key can be produced which is guaranteed as secure (i.e. the eavesdropper has no information about), otherwise no secure key is possible and communication is aborted.

The security of quantum cryptography relies on the foundations of quantum mechanics, in contrast to traditional public key cryptography which relies on the computational difficulty of certain mathematical functions, and cannot provide any indication of eavesdropping or guarantee of key security.

Quantum cryptography is only used to produce and distribute a key, not to transmit any message data. This key can then be used with any chosen encryption algorithm to encrypt (and decrypt) a message, which can then be transmitted over a standard communication channel. The algorithm most commonly associated with QKD is the one-time pad, as it is likely to be unbreakable when used with a secret, random key.

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.

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.

Polarized photons - Charles H. Bennett and Gilles Brassard (1984)

This protocol, known as BB84 after its inventors and year of publication, was originally described using photon polarization states to transmit the information. However any two pairs of conjugate states can be used for the protocol, and many optical fibre based implementations described as BB84 use phase encoded states. The sender (traditionally referred to as Alice) and the receiver (Bob) are connected by a quantum communication channel which allows quantum states to be transmitted. In the case of photons this channel is generally either an optical fibre or simply free space. In addition they communicate via a public classical channel, for example using radio waves or the internet. Neither of these channels need to be secure; the protocol is designed with the assumption that an eavesdropper (referred to as Eve) can interfere in any way with both.

The security of the protocol comes from encoding the information in non-orthogonal states. Quantum indeterminacy means that these states cannot in general be measured without disturbing the original state (see No cloning theorem). BB84 uses two pairs of states, with each pair conjugate to the other pair, and the two states within a pair orthogonal to each other. Pairs of orthogonal states are referred to as a basis. The usual polarization state pairs used are either the rectilinear basis of vertical (0°) and horizontal (90°), the diagonal basis of 45° and 135° or the circular basis of left- and right-handedness. Any two of these bases are conjugate to each other, and so any two can be used in the protocol. Below the rectilinear and diagonal bases are used.

Basis	0	1
X

The first step in BB84 is quantum transmission. Alice creates a random bit (0 or 1) and then randomly selects one of her two bases (rectilinear or diagonal in this case) to transmit it in. She then prepares a photon polarization state depending both on the bit value and basis, as shown in the table to the left. So for example a 0 is encoded in the rectilinear basis (+) as a vertical polarization state, and a 1 is encoded in the diagonal basis (x) as a 135° state. Alice then transmits a single photon in the state specified to Bob, using the quantum channel. This process is then repeated from the random bit stage, with Alice recording the state, basis and time of each photon sent.

Quantum mechanics (particularly quantum indeterminacy) says there is no possible measurement that will distinguish between the 4 different polarization states, as they are not all orthogonal. The only measurement possible is between any two orthogonal states (a basis), so for example measuring in the rectilinear basis will give a result of horizontal or vertical. If the photon was created as horizontal or vertical (as a rectilinear eigenstate) then this will measure the correct state, but if it was created as 45° or 135° (diagonal eigenstates) then the rectilinear measurement will instead return either horizontal or vertical at random. Furthermore, after this measurement the photon will be polarized in the state it was measured in (horizontal or vertical), with all information about its initial polarization lost.

As Bob does not know the basis the photons were encoded in, all he can do is select a basis at random to measure in, either rectilinear or diagonal. He does this for each photon he receives, recording the time, measurement basis used and measurement result. After Bob has measured all the photons, he communicates with Alice over the public classical channel. Alice broadcasts the basis each photon was sent in, and Bob the basis each was measured in. They both discard photon measurements (bits) where Bob used a different basis, which will be half on average, leaving half the bits as a shared key.

Alice's random bit	0	1	1	0	1	0	0	1
Alice's random sending basis			X		X	X	X
Photon polarization Alice sends
Bob's random measuring basis		X	X	X		X
Photon polarization Bob measures
PUBLIC DISCUSSION OF BASIS
Shared secret key	0		1			0		1

To check for the presence of eavesdropping Alice and Bob now compare a certain subset of their remaining bit strings. If a third party has gained any information about the photons polarization it will have introduced errors in Bobs measurements. If more than $p$ bits differ they abort the key and try again, possibly with a different quantum channel, as the security of the key cannot be guaranteed. $p$ is chosen so that if the number of bits known to Eve is less than this, privacy amplification can be used to reduce Eve's knowledge of the key to an arbitrarily small amount, by reducing the length of the key.

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 with 100% probability. 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, any attempt at eavesdropping by Eve will ruin these correlations, in a way that Alice and Bob can detect.

Privacy amplification and information reconciliation

The quantum cryptography protocols described above will provide Alice and Bob with nearly identical shared keys, and also with an estimate of the discrepancy between the keys. These differences can be caused by eavesdropping, but will also be caused by imperfections in the transmission line and detectors. As it is impossible to distinguish between these two types of errors, it is assumed all errors are due to eavesdropping in order to guarantee security. Provided the error rate between the keys is lower than a certain threshold (20% as of April 2007), two steps can be performed to first remove the erroneous bits and then reduce Eve's knowledge of the key to an arbitrary small value. These two steps are known as information reconciliation and privacy amplification respectively, and were first described in 1992.

Information reconciliation is a form of error correction carried out between Alice and Bob's keys, in order to ensure both keys are identical. It is conducted over the public channel and as such it is vital to minimise the information sent about each key, as this can be read by Eve. A common protocol used for information reconciliation is the cascade protocol, proposed in 1994 . This operates in several rounds, with both keys divided into blocks in each round and the parity of those blocks compared. If a difference in parity is found then a binary search is performed to find and correct the error. If an error is found in a block from a previous round that had correct parity then another error must be contained in that block; this error is found and corrected as before. This process is repeated recursively, which is the source of the cascade name. After all blocks have been compared, Alice and Bob both reorder their keys in the same random way, and a new round begins. At the end of multiple rounds Alice and Bob will have identical keys with high probability, however Eve will have gained additional information about the key from the parity information exchanged.

Privacy Amplification is a method for reducing (and effectively eliminating) Eve's partial information about Alice and Bob's key. This partial information could have been gained both by eavesdropping on the quantum channel during key transmission (thus introducing detectable errors), and on the public channel during information reconciliation (where it is assumed Eve gains all possible parity information). Privacy amplification uses Alice and Bob's key to produce a new, shorter key, in such a way that Eve has only negligible information about the new key. This can be done using a universal hash function, chosen at random from a publicly known set of such functions, which takes as its input a binary string of length equal to the key and outputs a binary string of a chosen shorter length. The amount by which this new key is shortened is calculated, based on how much information Eve could have gained about the old key (which is known due to the errors this would introduce), in order to reduce the probability of Eve having any knowledge of the new key to a very low value.

Implementations

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. 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 between two of the Canary Islands, achieved by a European collaboration using entangled photons (the Ekert scheme) in 2006, and using BB84 enhanced with decoy states in 2007 . The experiments suggest 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 ESA Space Debris 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.

The DARPA Quantum Network, a 10-node quantum cryptography network has been running since 2004 in Massachusetts, USA. It is being developed by BBN Technologies, Harvard University, Boston University and QinetiQ.

There are currently three companies offering commercial quantum cryptography systems; id Quantique (Geneva), MagiQ Technologies (New York) and SmartQuantum (France). Several other companies also have active research programmes, including Toshiba, HP, IBM, Mitsubishi, NEC and NTT (See External links for direct research links).

Quantum encryption technology provided by the Swiss company Id Quantique was used in the Swiss canton (state) of Geneva to transmit ballot results to the capitol in the national election occurring on Oct. 21, 2007.[10]

In 2004, the worlds first bank transfer using quantum cryptography was carried in Vienna. An important cheque, which needed absolute security, was transmitted from the Mayor of the city to an Austrian bank.[11]

Attacks

Quantum cryptography is vulnerable to a man-in-the-middle attack when used without authentication to the same extent as any classical protocol, since no principle of quantum mechanics can distinguish friend from foe. As in the classical case, Alice and Bob cannot authenticate each other and establish a secure connection without some means of verifying each other's identities (such as an initial shared secret). If Alice and Bob have an initial shared secret then they can use an unconditionally secure authentication scheme (such as Carter-Wegman,) along with quantum key distribution to exponentially expand this key, using a small amount of the new key to authenticate the next session. Several methods to create this initial shared secret have been proposed, for example using a 3rd party or chaos theory.

Because currently a dedicated fibre optic line (or line of sight in free space) is required between the two points linked by quantum cryptography, a denial of service attack can be mounted by simply cutting or blocking the line or, perhaps more surreptitiously, by attempting to tap it.

Other attacks target the classical endpoints of the connection and depend on implementation details. 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. Adi Shamir proposed an endpoint attack which does not require physical access to the endpoints: 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 reflects some of Mallory's light, revealing the state of Alice's polarizer. While this attack is easy to avoid, for example most implementations use the photons phase and not its polarization to encode the information, it is an example of a side channel attack which targets the implementation of the protocol instead of the protocol directly.

Single photon sources are needed in order to provide perfect secrecy using the BB84 protocol. Today's light source equipment produces photons in short laser pulses containing very few photons in each pulse. Some pulses don't even contain any photons, as a result of the low average number of photons per pulse. As a result a so called Photon Number Splitting (PNS) attack can be mounted. She keeps half of the photons in her quantum memory and forwards the remaining photons to Bob. When the bases are revealed during the secret key reconcilation process, she measures the photons she has kept and obtains the correct polarization and hence the correct value of the corresponding secret key bit. This attack fails whenever (by chance) Alice sends a single photon instead of a packet of photons. In this case, Eve will have a 50% chance of seeing that photon, if she does then Alice and Bob will know of her presence, and if she doesn't see it then she cannot reproduce the entire bit string.

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 Wolfson College, University of Oxford, developed a different approach to quantum cryptography based on peculiar quantum correlations known as quantum entanglement.

Prospects

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.

See also

• Secure Communication based on Quantum Cryptography (SECOQC)
• Quantum Information Science
• Quantum Computing
• Quantum fingerprinting
• Quantum digital signature

External links

• General and Review
  • Scientific American Magazine (January 2005 Issue) Best-Kept Secrets Non-technical article on quantum cryptography
  • Physics World Magazine (March 2007 Issue) Non-technical article on current state and future of quantum communication
  • arXiv:quant-ph/0702202v3 March 2007 review of Quantum Cryptography
  • InterQuanta Quantum Information, Overview of Decoy-State and Free-Space QKD
  • SECOQC White Paper on Quantum Key Distribution and Cryptography European project to create a large scale quantum cryptography network, includes discussion of current QKD approaches and comparison with classical cryptography
  • ARDA Quantum Cryptography Roadmap

• More Specific Information
  • Description of entanglement based quantum cryptography from Artur Ekert[12]
  • Description of BB84 protocol and privacy amplification[13]
  • Original paper on the BB84 Protocol for Quantum Cryptography[14]
  • Original paper on Entanglement-based quantum cryptography [15]
  • Early article on experimental quantum cryptography [16]
  • Error Detection and Correction in Quantum Cryptography (Cascade) [17]

• Further Information
  • Quantiki.org - Quantum Information news and wiki
  • Quantum Cryptography Mailing List
  • European portal of Quantum Cryptography

• Quantum Cryptography Research Groups
  • Experimental Quantum Cryptography with Entangled Photons
  • NIST Quantum Information Networks

• Companies selling quantum devices for cryptography
  • id Quantique sells Quantum Key Distribution products
  • MagiQ Technologies sells quantum devices for cryptography
  • SmartQuantum Hardware solutions for quantum and digital cryptogaphy

• Companies with quantum cryptography research programmes
  • Toshiba
  • HP
  • IBM
  • Mitsubishi
  • NEC
  • NTT