Quantum cryptography

Quantum cryptography currently has two aspects, both mostly theoretical. The first is quantum key exchange, the second is the effect of quantum computing on cryptanalysis. The basic idea in quantum key exchange is to use the "noisy" properties of light to render incoherent an image that acts to complement a secret key. This image can be represented in a number of ways, but the ability to decode that image rests upon an understanding of how it was made. No way to intercept the transmission without changing it is possible, so key information can be exchanged with great confidence it has been transmitted secretly. Using quantum superposition as a part of the computation, quantum computing will considerably extend the reach of cryptanalysis, making brute force key space searches much more effective -- if such computers ever become possible in actual practice.

Table of contents
1 Quantum Key Exchange
2 Quantum Computing applications for Cryptanalysis
3 Prospects
4 References

Quantum Key Exchange

This is a particular approach to crytography which appears to offer a very secure, albeit expensive, and low data rate, communications channel.

The most straightforward application is in distribution of secret keys. The rate of transmission will likely be low, for technical reasons, but the transmission will be secure at our present understanding of quantum mechanics. No informed observer has suggested any way around this; it is widely believed there can be no such way. By taking advantage of existing high quality encryption algorithms, this initial secure transfer can be leveraged to achieve a secure transmission of large amounts of data at much higher speeds. Quantum key exchange may, thus, become an excellent alternative to the Diffie-Hellman key exchange algorithm.

The advantage of quantum key exchange over traditional key exchange methods is the certainty that the key exchange cannot be compromised. The exchange can be shown to be secure in a very strong sense, without relying on the intractability of one or more mathematical problems. Even assuming eavesdroppers with unlimited computing power, the laws of quantum physics guarantee (though only probabilistically) that the key exchange will be secure, given a few other assumptions.

The information is exchanged by observations of quantum states. Typically photons are put into a particular state by the sender and then observed by the recipient. Because of Heisenberg's Uncertainty Principle, certain quantum information occurs as conjugates (superposition) that cannot be simultaneously measured . Depending on how an observation is carried out, different aspects of the system can be measured -- for example, polarizations of photons can be expressed as any of three different types: rectilinear, circular, and diagonal -- but any observation (including by any eavesdropper) changes the values of the conjugates. Thus, if the receiver and sender do not agree on what basis of a quantum system they are using as bases, the receiver or eavesdropper will destroy the sender's information without gaining any useful information, and, depending on the protocols being used, may betray his/her presence.

Ideally, each pulse should consist of a single photon. If this is impossible, and the number of photons received is Poisson-distributed, the average number of photons in each pulse should be slightly larger than the logarithm of the number of bits in a message. Fewer, and a pulse may be absent; more, and the polarization of a pulse can be detected without altering it.

How it would work

Alice wants to sent a message to Bob. They both have devices that can generate pulses of light in any of the different polarizations, and also devices that detect the polarization of light.

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 l "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 - l - 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/ln2 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 l iterations, Alice and Bob conclude their strings agree with low probability of error (2^-l).


The roots of quantum cryptography are in a proposal by Stephen Weisner called "Conjugate Coding" from the early 1970s. It was eventually published in 1983 in Sigact News, and by that time Bennett and Brassard, who were familiar with Weisner's ideas, were ready to publish ideas of their own. They produced "BB84" the first quantum key exchenge protocol, in 1984, but it was not until 1991 that the first experimental prototype based on this protocol was made operable (over a distance of 32 centimeters). More recent systems have been tested successfully on fiber optic cable over distances in the kilometers.

Quantum Computing applications for Cryptanalysis

Because quantum states can exist in superposition (ie, entangled), a new paradigm for computation is possible. Peter Shor of Bell Labs proved the possibility, and various teams have demonstrated one or another aspect of quantum computer engineering in the years since. Thus far, only very limited proof of possibility designs have been demonstrated. There is, at this writing, no credible prospect of an actual, usable, quantum computer.

However, were a quantum computer to be built, many things would change. Parallel computation would likely become the norm, and some aspects of cryptography would change.

In particular, since a quantum computer would be able to conduct extremely fast brute force key searches, key lengths now considered effectively beyond any attacker's resources would become practical. Key lengths necessary to be beyond a quantum computer's capacity would be longer, probably considerably longer. Some popular writers have declared that no encryption could be unbroken when quantum computers become available. This is certainly false, for increases in key lengths are easy to manage as each one bit increase in key length doubles the key space 'volume' and so doubles the work effort required of the searching computer (quantum or otherwise). It will, almost certainly, remain easier to add bits to key lengths than to brute force search the resulting key spaces, even with quantum computers.

A second possibliity is that increased computational power may make possible non brute force key search attacks against one or more currently impregnable algorithms, or classes of algorithms. For instance, not all progress in prime factorization has been due to algorithmic improvements. Some has been due to increasing computer power. This may be expected to continue. What cannot be anticipated is a theoretical breakthrough, requiring quantum computing, which would make possible currently impractical (or even unknown) attacks. In the absence of a method for predicting breakthroughs, we will simply have to wait.


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. For the foreseeable future, actual use of quantum key exchanges in cryptography will likely be confined to exotic situations in which the quite considerable limitations are tolerable. Perhaps some military uses, for instance. Were a way of isolating some quantum state from all perturbing interactions to be discovered, this technique shows promise of largely replacing such protocols as Diffie-Hellman key exchange.

Quantum computing, if possible at all, has much development ahead before it becomes any sort of reality. A reasonable estimate is 'many years' at least. Until then, cryptanalysis on a quantum computer will remain indeterminate.



copyright 2004 FactsAbout.com