QUANTUM CRYPTOGRAPHY

QUANTUM CRYPTOGRAPHY

Jeff Heuer. 4.28.98
EECS 598, Winter 98, Dr. Peter Honeyman

Download Postscript

INTRODUCTION.

Quantum Cryptography was first posited in an article by Stephen Wiesner entitled "Conjugate Coding", written in the late 1960's. In this article, Wiesner proposed methods of using quantum physics to create unforgable bank notes and build what he termed a "multiplexing channel" (now known as "oblivious transfer"). This paper went unpublished and (more-or-less) unnoticed until a collaboration with Bennett, Brassard, and Breidbart in 1979 yielded a new paper [1], applying quantum theory to the new science of public key cryptography. Quantum techniques were initially considered infeasible for real use, due to technological limitations effecting the storage and transmission of photons. Subsequent technological improvements have resulted in working prototypes of quantum cryptographic transmission channels, with the first fully-functional model being built in 1989 ¹. Although this apparatus was only able to work successfully over a distance of 32 cm., there is no theoretical limit to the distance from which quantum systems could be removed from each other. Quantum technologies are also being investigated for application towards general computational problems, separate from their applications towards cryptography.

¹ For an in-depth discussion of the prototype, see [1].

Quantum Cryptography is based on a fundamentally different transmission mechanism than conventional cryptography. While the vast majority of published cryptography work has dealt with systems based on sending short pulses of electricity over wire (the basis of nearly all modern computing), quantum cryptography uses photons, which are the most elementary particle of light. Photons (or as we will see later, more realistically, short pulses of very dim light) can be sent through open air or via a light-transmitting medium such as fiber optic cable. One of the fundamental characteristics of a photon is its polarization, or "spin". The polarization of a photon is measured according to one of three possible conjugate bases: rectilinear, diagonal, or circular, and each measurement yields one of two possible polarizations: 0° (horizontal) or 90° (vertical), 45° or 135°, and right-circular or left-circular, respectively. The term "conjugate" used in Wiesner's original work refers to a pair of bases for which the measurement with respect to one necessarily randomizes the measurement with respect to the other. The three bases ennumerated above are all conjugates to each other, and this measurment randomization is the fundamental characteristic of quantum particles taken advantage of by quantum cryptography.

The relevant behavior characteristic which quantum cryptography's resistance to eavesdropping is based on is the Heisenberg Uncertainty Principal. In its most common manifestation, Heisenberg's Uncertainty shows the impossibility of accurately measuring both the position and momentum of an elementary physical particle at the same time. Heisenberg's relevance to quantum cryptography is that the polarization of a photon can only be measured in terms of a single basis this act of measuring destroys the information necessary to measure polarization with respect to any other basis. This characteristic allows for two desirable features of a cryptosystem:

It is impossible for an eavesdropper to reliably read transmitted data without access to information used to form the transmission. This impossibility is "hard" in that it is based on a physical principle and withstands an attack even from an attacker with unlimited computing power.
Even eavesdropping which desires to be "passive" disturbs the transmission in an unpredictable way. This disturbance is likely to be noticed by legitimate users of the system.

Together, these features make eavesdropping in a quantum channel both unproductive (atleast with respect to the pure protocol) and subject to detection. Additionally, the difficulty in reliably storing photon particles in a manner which preserves their state further complicates eavesdropping (e.g., forward secrecy is more easily accomplished, since the archival of old transmissions for substantial lengths of time is not feasible).

To date, quantum cryptography has been applied to many problems, including key distribution, oblivious transfer, bit commitment, and coin-tossing. To illustrate how these principles can be applied in practice, let's walk through a hypothetical key distribution protocol using a quantum transmission channel.

Alice and Bob wish to agree upon a random session key using a channel subject to eavesdropping. A combination of quantum transmission and public discussion between Alice and Bob will be used to arrive at a shared, secret data string. The process consists of two parts: the original transmission and discussion, which yields a partially shared, partially leaked data string, and a process of data reconciliation and privacy amplification, to reduce this string into a fully shared, fully private one.

We will make use of two canonical bases: rectilinear and circular. Thus all measurements will be performed using one of these bases. This yields four canonical polarizations: vertical, horizontal, right-circular, and left-circular. All transmitted particles will have one of the canonical polarizations. It should be noted that in theory any two of the three bases could be used here. In practice, the selection of canonical bases would most likely depend on the configuration of detectors used in a specific implementation.

RAW PROTOCOL.

1
2
3
4
5
6
7	0	1	0	1	0

Alice sends a random stream of photons, each polarized either horizontal (), vertical (), right-circular (), or left-circular ().
For each photon received, Bob randomly chooses to measure either its rectilinear polarization () or circular polarization ().
Results of Bob's measurements
Bob tells Alice which basis he used to measure each photon
Alice tells Bob which bases he chose correctly (i.e., according to the basis Alice intended)
All photons which were measured using an incorrect basis are discarded
The remaining photons are converted to bits according to a predetermined coding scheme. Here, horizontal () and left-circular () photons are interpreted as binary 0, and likewise vertical () and right-circular () photons as binary 1.

These seven steps constitute what is known as a raw quantum transmission. Several factors render this protocol inadequate for real world use — it must be augmented to account for technological limitations and channel noise. These modifications should allow Alice and Bob to communicate using available technology and take into account the error rates these technologies are prone to. In general, if the error rate is below some threshold, it will be interpreted as simply the result of a reasonable amount of channel noise. If the error rate is above the threshold Alice and Bob will suspect that the presence of channel eavesdropping disturbed their transmission.

It is currently not technologically feasible to accurately transmit a single photon. Instead, brief pulses of very dim light are used. According to [2], "It is much easier to produce a coherent pulse, which may be regarded as the superposition of quantum states with 0, 1, 2,… photons; or an incoherent pulse, which may be regarded as a statistical mixture of coherent states." ² This currently-necessary modification to the originally proposed protocol is one of its potential weaknesses. As one moves along the continuum from single photon to continuous light beam, particle behavior moves from that described by quantum mechanics to that described by classical mechanics. As the particles behave more and more classicly, some of the system's desirable characteristics weaken, and this factor is the basis of a large class of published attacks, known as beamsplitting. Imagine a system which for practical reasons used a stream comprised of n number of consecutive, identically polarized photons to transmit each bit of information, rather than just a single photon as in the pure protocol. The potential would exist for an attacker to selectively measure every n^th photon by placing a semi-silvered mirror in the light path and diverting a fraction of the light onto her own set of detectors. At this point the eavesdropper may either randomly choose a basis to measure each photon in, or if technologically sophisticated, simply store the diverted photon stream until the public discussion between Alice and Bob has revealed which basis is appropriate for each photon. This form of eavesdropping will be difficult to detect because a significant fraction of each pulse still passes through to Bob undisturbed. The pulses received by Bob will be weaker due to the diverted energy — this is the only clue which could tip off the legitimate channel users to the presence of an eavesdropper. The other primary class of published attacks on quantum systems is known as intercept and resend and is more intrusive. In an intercept and resend attack, the eavesdropper reads a subset of the transmission, preventing its receipt by Bob. For each read photon, a new photon is resent to Bob whose polarization corresponds to that read by the eavesdropper. The intercepted photon may or may not have been read using the proper basis by the eavesdropper — this is the source of the disturbance introduced by the attacker. The retransmitted photon has a 50% chance of being of a different polarization than the originally transmitted one.

² [2] p. 6

Even in the absence of tampering from an eavesdropper, it is very likely that the stream of photons sent by Alice will not correspond exactly with the stream received by Bob. Light pulses are kept very brief and dim — the longer and brighter they are, the more they resemble classical particle pulses and lose their quantum behavior, as discussed above. However, this also means that detecting the pulse is more difficult and error-prone. While detectors may occasionally miss a pulse because of its weak strength, they also sometimes signal the receipt of a pulse even when none was sent. This phenomenon is known as a "dark count". Both of these types of errors are unavoidable with current detectors and any practical quantum protocol must have the ability to recover from this type of noise Following completion of the raw quantum transmission, Alice and Bob will have data strings which are partially shared (the exception being errors introduced in transmission) and about which an eavesdropper has at most 1/2 a bit of information about each bit in the transmitted string (the probability that they chose the correct basis with which to measure an intercepted or deflected photon). What is now necessary is for Alice and Bob to engage in a reconciliation process which will both eliminate random noise-induced errors and aid in the detection of an eavesdropper. This process involves comparison of the polarizations of a random subset of the Alice's broadcast transmission to Bob's received transmission. [2] suggests first rearranging the strings according to a predetermined random permutation in order to spread errors evenly throughout the entire string. After permuted, the string is segmented into a series of blocks of size k. Block size is chosen so that each block is likely to have at most one error. Alice and Bob then perform a parity calculation on each block and compare their results. If the parity of a block does not correspond between Alice and Bob, this block is successively broken down into smaller segments, which are then compared as the original block, until the discrepancy is located and corrected. In order to prevent the error-correction process from leaking any more information than may already have been divulged, one bit is discarded from each compared block, according to a predetermined scheme such as always discarding the final bit of a parity-divulged block. This comparison and discarding process is repeated with increasing block sizes until Alice and Bob are satisfied that the chance of persistent errors is slim. This can be done by keeping track of the ratio of error blocks to correct blocks, or simply waiting for a number n of consecutive correct blocks. All of the actual parameters (block size, number of repeat tests, acceptable chance of remaining error) to be used in this discussion are determined by detector performance, physical implementation specifics, and empirical data. ³ To give a feel for real-world error rates, the apparatus constructed in [2] had an error rate of 3.95% without eavesdropping, and when subjected to a beamsplitting attack which diverted approximately 1/8 of the pulse, the error rate increased to 8%.

³ Realistic empirical values can be found on pp. 16-19 of [2]

Upon completion of this process we can be confident that Alice and Bob have a shared collection of bits, about which an eavesdropper may have partial information. At this point a technique of privacy amplification can be used to arrive at a smaller, but almost perfectly secret collection of bits. A new string will be constructed, based solely on information from the original string. One method of achieving this is by defining each bit of the new privacy-amplified string as the parity of n specific bits of the original (shared, but not entirely private) string. For example the first new bit could be defined as the parity of old bits 13, 48, 79, 111, 112, 140, 181, and 200. Using this algorithm, the eavesdropper would need to have perfect information of all 8 bits to be confident of the value of the new bit, and otherwise has only a 50% chance of correctly guessing the result. In this way, the eavesdropper's partial information of the original string is unlikely to be sufficient to yield any information of the new string.

Upon completion of the privacy amplification process, Alice and Bob have a quantity which will function well as a session key. They can be confident they share the same value and that it is unlikely that an eavesdropper has significant knowledge of this value. While this form of key generation can be accomplished more readily using conventional means, quantum cryptography holds the promise near-perfect of privacy based upon elementary scientific law. There are few other techniques which can appeal to such a solid cryptographic foundation.

BIBLIOGRAPHY.

[1] Bennett, C. H., G. Brassard, S. Breidbart and S. Wiesner, "Quantum cryptography, or unforgeable subway tokens", Advances in Cryptology: Proceedings of Crypto '82 , August 1982, Plenum Press, pp. 267 - 275. RETURN

[2] Bennett, C. H., Bessette, F., Brassard, G., Salvail, L. and Smolin, J., "Experimental quantum cryptography", Journal of Cryptology, vol. 5, no. 1, 1992, pp. 3 - 28. Preliminary version in Advances in Cryptology — Eurocrypt '90 Proceedings, May 1990, Springer - Verlag, pp. 253 - 265. RETURN

[3] Bennett, C. H., Brassard, G., Crépeau, C. and Skubiszewska, M. H., "Practical quantum oblivious transfer", Advances in Cryptology — Crypto '91 Proceedings, August 1991, Springer - Verlag, pp. 351 - 366.

[4] Bennett, C. H. and G. Brassard, "An update on quantum cryptography", Advances in Cryptology: Proceedings of Crypto '84 , August 1984, Springer - Verlag, pp. 475 - 480.

[5] Bennett, C. H., Brassard, G. and Ekert, A. K., "Quantum cryptography", Scientific American, October 1992, pp. 50 - 57. Appeared in December 1992 as translation into German (Spektrum der Wissenschaft, pp. 96 - 104), Italian (Le Scienze, pp. 84 - 93), Japanese (Saiensu, pp. 50 - 60), and Polish (Swiat Nauki, pp. 28 - 37), among others.

[6] Brassard, G., "A bibliography of quantum cryptography", Sigact News 75