Quantum cryptography

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 provably secure when used with a secret, random key [C. E. Shannon , Bell Syst. Tech. J. 28, 656 (1949)] .

Quantum key exchange

Quantum communication involves encoding information in quantum states, or qubits, as opposed to classical communications use of bits. Usually, photons are used for these quantum states. Quantum cryptography exploits certain properties of these quantum states to ensure its security. There are several different approaches to quantum key distribution, but they can be divided into two main categories depending of which property they exploit.

; Prepare and measure protocols : Unlike in classical physics, the act of measurement is an integral part of quantum mechanics. In general, measuring an unknown quantum state will change that state in some way. This is known as quantum indeterminacy, and underlies results such as the Heisenberg uncertainty principle, information-disturbance theorem and no cloning theorem. This can be exploited in order to detect any eavesdropping on communication (which necessarily will involve measurement), and more importantly calculate the amount of information which has been intercepted.

; Entanglement based protocols : The quantum states of two (or more) separate objects can become linked together in such a way that they must be described by a combined quantum state, not as individual objects. This is known as Entanglement and means, for example, performing a measurement on one object will affect the other. If an entangled pair of objects is shared between two parties, anyone intercepting either particle will alter the overall system, allowing their presence (and the amount of information they have gained) to be determined.

These two approaches can both further be divided into three families of protocols; discrete variable, continuous variable and distributed phase reference coding. Discrete variable protocols were the first to be invented, and they remain the most widely implemented. The other two families are mainly concerned with overcoming practical limitations of experiments. The two protocols described below both use discrete variable coding.

BB84 protocol - 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 broadcast radio 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.

The probability Eve chooses the incorrect basis is 50% (assuming Alice chooses her basis randomly), and if Bob measures this intercepted photon in the basis Alice sent he will get a random result, i.e. an incorrect result with probability of 50%. The probability an intercepted photon generates an error in the key string is then 50% x 50% = 25%. If Alice and Bob publicly compare $n$ of their key bits (thus discarding them as key bits, as they are no longer secret) the probability they find disagreement and identify the presence of Eve is

$P\_d\; =\; 1\; -\; left(frac\{3\}\{4\}\; ight)^n$

So to detect an eavesdropper with probability $P\_d\; =\; 0.999999999$ Alice and Bob need to compare $n\; =\; 72$ key bits.

Security Proofs

The above is just a simple example of an attack. If Eve is assumed to have unlimited resources, for example classical and quantum computing power, there are many more attacks possible. BB84 has been proven secure against any attacks allowed by quantum mechanics, both for sending information using an ideal photon source which only ever emits a single photon at a time [P. W. Shor and J. Preskill, Physical Review Letters 85, 441(2000)] , and also using practical photon sources which sometimes emit multiphoton pulsesD. Gottesman, H.-K. Lo, N. L¨utkenhaus, and J. Preskill,Quant. Inf. Comp. 4, 325 (2004)] . These proofs are unconditionally secure in the sense that no conditions are imposed on the resources available to the Eavesdropper, however there are other conditions required:
# Eve cannot access Alice and Bob's encoding and decoding devices.
# The random number generators used by Alice and Bob must be trusted and truly random (for example a Quantum random number generator).
# The classical communication channel must be authenticated using an unconditionally secure authentication scheme.

Man in the middle attack

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, [M. N. Wegman and J. L. Carter, "New hash functions and their use in authentication andset equality, Journal of Computer and System Sciences", 22, pp 265-279, (1981)] ) along with quantum key distribution to exponentially expand this key, using a small amount of the new key to authenticate the next session [Romain Alleaume, et al. "SECOQC White Paper on Quantum Key Distribution and Cryptography" arXiv:quant-ph/0701168v1 pp. 7 (2007) ( [http://arxiv.org/abs/quant-ph/0701168] )] . Several methods to create this initial shared secret have been proposed, for example using a 3rd party [ Z. Zhang, J. Liu, D. Wang and S. Shi “Quantum direct communication with authentication” Phys. Rev. A 75, 026301 (2007)] or chaos theory [D. Huang, Z. Chen, Y. Guo and M. Lee "Quantum Secure Direct Communication Based on Chaos with Authentication", Journal of the Physical Society of Japan Vol. 76 No. 12, 124001 (2007) ( [http://jpsj.ipap.jp/link?JPSJ/76/124001/] )] .

Photon number splitting attack

In the BB84 protocol Alice sends quantum states to Bob using single photons. In practice many implementations use laser pulses attenuated to a very low level to send the quantum states. These laser pulses contain a very small number of photons, for example 0.2 photons per pulse, which are distributed according to a Poissonian distribution. This means most pulses actually contain no photons (no pulse is sent), some pulses contain 1 photon (which is desired) and a few pulses contain 2 or more photons. If the pulse contains more than one photon, then Eve can split off the extra photons and transmit the remaining single photon to Bob. This is the basis of the photon number splitting attack [G. Brassard, N. Lütkenhaus, T. Mor, and B. C. Sanders. "Limitations on practical quantum cryptography." Physical Review Letters, 85(6):1330+ (2000)] , where Eve stores these extra photons in a quantum memory until Bob detects the remaining single photon and Alice reveals the encoding basis. Eve can then measure her photons in the correct basis and obtain information on the key without introducing detectable errors.

Even with the possibility of a PNS attack a secure key can still be generated, as shown in the GLLP security proof, however a much higher amount of privacy amplification is needed reducing the secure key rate significantly (with PNS the rate scales as $t^2$ as compared to $t$ for a single photon sources, where $t$ is the transmittance of the quantum channel).

There are several solutions to this problem. The most obvious is to use a true single photon source instead of an attenuated laser. While such sources are still at a developmental stage QKD has been carried out successfully with them [P. M. Intallura, , M. B. Ward, O. Z. Karimov, Z. L. Yuan, P. See, A. J. Shields, P. Atkinson, and D. A. Ritchie, Appl. 43 Phys. Lett. 91, 161103 (2007)] . However as current sources operate at a low efficiency and frequency key rates and transmission distances are limited. Another solution is to modify the BB84 protocol, as is done for example in the SARG04 protocol [V. Scarani, A. Ac´ın, G. Ribordy and N. Gisin, Phys. Rev. Lett. 92, 057901 (2004)] , in which the secure key rate scales as $t^\{3/2\}$. The most promising solution is the decoy state idea [W.-Y. Hwang, Phys. Rev. Lett. 91, 057901 (2003)] , in which Alice randomly sends some of her laser pulses with a lower average photon number. These decoy states can be used to detect a PNS attack, as Eve has no way to tell which pulses are signal and which decoy. Using this idea the secure key rate scales as $t$, the same as for a single photon source. This idea has been implemented successfully in several QKD experiments [Z. L. Yuan, A. W. Sharpe, and A. J. Shields, Appl. Phys.Lett. 90, 011118 (2007)] , allowing for high key rates secure against all known attacks.

Hacking attacks

Hacking attacks target imperfections in the implementation of the protocol instead of the protocol directly. 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. Another common class of attacks is the Trojan horse attack [Vakhitov, A. V. Makarov and D. R. Hjelme, J. Mod. Opt. 48, 2023 (2001)] 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. This attack is easy to avoid, for example using an optical isolator to prevent light from entering Alice's system, and all other hacking attacks can similarly be defeated by modifying the implementation. Apart from Trojan horse there are several other known attacks including faked state attacks [V. Makarov and D. R. Hjelme, J. Mod. Opt. 52, 691. (2005)] , phase remapping attacks [ C.-H. F. Fung, B. Qi, K. Tamaki, and H.-K. Lo, Phys. Rev. A 75, 032314. (2007)] and time-shift attacks [B. Qi, C.-H. F. Fung, H.-K. Lo, and X. Ma, Quant. Info. Compu. 7, 43 (2007) ] . The time-shift attack has even been successfully demonstrated on a commercial quantum crypto-system [Y. Zhao, C.-H. F. Fung, B. Qi, C. Chen, and H.-K. Lo, arXiv:0704.3253 ] . This demonstration is the first successful demonstration of quantum hacking against a non-homemade quantum key distribution system.

Denial of service

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.

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
* Quantum cryptography protocol
* List of quantum cryptography protocols

External links

*General and Review
** [http://www.sciam.com/article.cfm?chanID=sa006&articleID=000479CD-F58C-11BE-AD0683414B7F0000 Scientific American Magazine (January 2005 Issue) Best-Kept Secrets] Non-technical article on quantum cryptography
** [http://physicsweb.org/articles/world/20/3/4/1 Physics World Magazine (March 2007 Issue)] Non-technical article on current state and future of quantum communication
** [http://arxiv.org/abs/0802.4155 arXiv:0802.4155 (quant-ph)] February 2008 review of Quantum Cryptography
** [http://arxiv.org/abs/quant-ph/0702202 arXiv:quant-ph/0702202v3] March 2007 review of Quantum Cryptography
** [http://www.secoqc.net/downloads/secoqc_crypto_wp.pdf 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
** [http://qist.lanl.gov/qcrypt_map.shtml ARDA Quantum Cryptography Roadmap]

*More Specific Information
** Description of entanglement based quantum cryptography from Artur Ekert [http://pass.maths.org.uk/issue35/features/ekert/index.html]
** Description of BB84 protocol and privacy amplification [http://www.ai.sri.com/~goldwate/quantum.html]
** Original paper on the BB84 Protocol for Quantum Cryptography [http://quantum.bbn.com/dscgi/ds.py/Get/File-18/BB84.pdf]
** Original paper on Entanglement-based quantum cryptography [http://quantum.bbn.com/dscgi/ds.py/Get/File-369/Ekert_-_QKD_Based_On_Bells_Theorem.pdf]

*Further Information
** [http://www.quantiki.org/wiki/index.php/Main_Page Quantiki.org - Quantum Information news and wiki]
** [http://fredhenle.net/bb84/ Interactive BB84 simulation]
** [http://research.physics.uiuc.edu/QI/Photonics/movies/bb84.swf Flash simulation of BB84]

*Quantum Cryptography Research Groups
** [http://www.quantenkryptographie.at/ Experimental Quantum Cryptography with Entangled Photons]
** [http://w3.antd.nist.gov/quin.shtml NIST Quantum Information Networks]

*Companies selling quantum devices for cryptography
** [http://idquantique.com id Quantique] sells Quantum Key Distribution products
** [http://magiqtech.com MagiQ Technologies] sells quantum devices for cryptography
** [http://www.quintessencelabs.com Quintessence Labs] Solutions based on continuous wave lasers
** [http://www.smartquantum.com SmartQuantum] Hardware solutions for quantum and digital cryptography

*Companies with quantum cryptography research programmes
** [http://www.toshiba-europe.com/research/crl/qig/quantumkeyserver.html Toshiba]
** [http://www.hpl.hp.com/research/qip/ Hewlett Packard]
** [http://www.almaden.ibm.com/st/quantum_information/qcrypt/ IBM]
** [http://global.mitsubishielectric.com/bu/security/rd/rd03.html Mitsubishi]
** [http://www.nec.co.jp/rd/Eng/Topics/index.html NEC]
** [http://www.brl.ntt.co.jp/E/research/qo/qo.html NTT]

References

----