|
Quantum cryptography currently has two aspects. The first is quantum key exchange, a method for securing communications based on quantum mechanics. The second is the conjectured effect of quantum computing on cryptanalysis, although it
is currently, like quantum computing itself, only a theoretical concept.
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.
Quantum key exchange
This is a particular approach to cryptography 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 subsequent 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 and funding, 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 every observation of those photons (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 send 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/ln 2 bits.
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 B1 and B2 and sends a pulse
of light. B1 selects the basis and B2 the polarization within that basis.
- Bob generates a random bit B3 and sets his polarization detector to that basis. He reads bit B4.
- 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:
- 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 exchange 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. Sending and receiving devices are now available commercially.
Quantum computing applications for cryptanalysis
Quantum computers have potential for use in 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 brute force attacker's resources
would become practical. Key lengths necessary to be beyond a quantum computer's capacity would be longer, probably considerably
longer. While some popular writers have declared that no encryption would remain secure when quantum computers become available,
it seems likely that simply adding bits to key lengths will prohibit brute force attacks, 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 factorisation has been due to algorithmic
improvements. Some has been due to increasing computer power, and the existence of working quantum computers may considerably
advance factorization thus increasing the vulnerability of some cryptographic algorithms. This much is perhaps foreseeable, if
not clearly. 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.
It is unknown whether there is a polynomial time encryption
algorithm for which decryption requires exponential time, even for
a quantum computer.
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
See also
|