**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 |

2 Quantum Computing applications for Cryptanalysis 3 Prospects 4 References |

## Quantum Key Exchange

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

The actual information exchange can occur in a number of forms. The first is by generating a one-time pad as follows:

- Alice generates two random bits B
_{1}and B_{2}and sends a pulse of light. B_{1}selects the basis and B_{2}the polarization within that basis. - Bob generates a random bit B
_{3}and sets his polarization detector to that basis. He reads bit B_{4}. - Bob and Alice tell each other B
_{3}and B_{1}over a public, but authenticated, channel. If they agree, they add B_{2}and B_{4}to their pads, knowing that they are the same unless Eve is listening (Eve doesn't know B_{1}at the time of Alice's pulse transmission).

To send a message:

- 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.
- 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).

### History

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

## Prospects

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.

## References