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 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 some understanding of how it was made. No one-to-one conversion process is avaliable, which makes the image itself is too incoherent to render, and hence without the secret key to seed the decryption process, the highly complex nature of the encrypted data would make it impossible to decrypt. Regardless of the complexity of the encryption -- any disturbance, as in optical eavesdropping of the transmission signal would corrupt the image, and render the data useless.

Table of contents 1 Quantum Key Exchange 2 How it would work 3 History 4 Quantum Computing applications for Cryptanalysis 5 Prospects 6 References

Quantum Key Exchange

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

The most straightforward application is in distribution of secret keys. The rate of transmission is very low, but it is provably secure. By taking advantage of existing key cryptographic algorithms, this initial transfer can be leveraged to achieve a secure transmission of large amounts of data at much higher speeds. Quantum cryptography may, thus, become an excellent alternative to the Diffie-Hellman key exchange algorithm. The information exchanged can then be used as a conventional key for further high security communication.

The advantage of quantum cryptography over traditional key exchange methods is the certain knowledge that the key exchange was not have been compromised. The exchange can be shown to be secure in a very strong sense, without making assumptions about the intractability of one or more mathematical problems. Even assuming eavesdroppers with unlimited computing power, the laws of physics guarantee (though only probabilistically) that the key exchange will have been 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 that cannot be measured simultaneously. Depending on how the observation is carried out, different aspects of the system can be measured -- for example, polarizations of photons can be expressed in any of three different bases: rectilinear, circular, and diagonal -- but any observation (including by any eavesdropper) randomizes 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 inadvertently destroy the sender's information without gaining any useful information, and, depending on the system protocols, 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 and Bob have devices that can generate pulses of light in any of the different polarizations and 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 potential 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 B₁ and B₂ and sends a pulse of light. B₁ selects the basis and B₂ the polarization within that basis.
2. Bob generates a random bit B₃ and sets his polarization detector to that basis. He reads bit B₄.
3. Bob and Alice tell each other B₃ and B₁. If they agree, they add B₂ and B₄ to their pads, knowing that they are the same unless Eve is listening (Eve doesn't know B₁).

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

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 cryptography 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 wirters have declared that no encryption could be unbroken when quantum computers become available. This is almost certainly false, for increases in key lengths are easy to manage, but each one bit increase doubles the key space 'volume' and so doubles the work effort required of the searching computer. 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 attacks. In the absence of a method for predicting breakthroughs, we will simply have to wait.

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. For the foreseeable future, actual use of quantum key exchanges in cryptography will likely be confined to exotic uses in which the 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 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, quantum cryptanalysis will remain indeterminate.

References

• D. Stucki, N. Gisin, O. Guinnard, G. Ribordy, H. Zbinden. Quantum Key Distribution over 67 km with a plug & play system (http://xxx.lanl.gov/abs/quant-ph/0203118)