Physics and Privacy
Some History
For hundreds of years attempts have been made to devise methods by which
the content of communications between parties can remain secret.
During this time there has been much development in two areas: the
production of new algorithms to encrypt the communications, and the production
in tandem of methods used to defeat those algorithms. Initially simple
substitution ciphers were used, where letters were replaced by other symbols
or letters. However, this method of coding data was broken using
frequency analysis, where the number of occurrences of each symbol in a
message were compared with the expected frequency of the letters a language.
Encryption techniques became more complex and secure in response, and were
matched by a similar increase in ability of the decryption techniques,
although some encryption schemes were considered perfectly secure for periods
of time (usually until a new technique was shown to break them).
This development and counter development between those who seek to communicate
in secret and those who seek to read the coded messages continues today.
The Current State of Cryptography
Encryption today is moving from a domain that concerned only governments,
the military, and spies, to becoming an everyday concern for businesses
and individuals as they attempt to communicate and store data in an increasing
networked world. Much of today's encryption is based on RSA public-key
algorithms. For simplicity, we will call the two parties attempting
to communicate Alice and Bob. In order for Bob to send a message
to Alice, Bob must first obtain the encryption key, which is known as Alice's
public key. This public key is not a secret, and the security of
the encryption algorithm is based on the fact that although data can be
encrypted with this public key, the same key cannot then be used to decrypt
the message. Bob then sends the encrypted message to Alice, who can
decrypt it using another key which is know only to her. Although
the public key cannot be used to decrypt the message directly, it is possible
to factor the public key into its two prime number factors, and then decrypt
the message using this new information. However, the two prime numbers
used to construct the public key are typically huge, and the factoring
process is extremely time consuming. Despite the advances in computer
power and number theory there are no publicly known techniques to factor
large numbers in better than exponential time. So for sufficiently
large keys, RSA can, in theory, keep data secret for considerable periods
of time from all but the most dedicated agencies. However, this may
change, even if a classical polynomial time factoring algorithm is never
found.
Quantum Computing
Traditional computers are based on binary digits (bits), with each each
bit capable of representing either 1 or 0 at any given time. Sequences
of bits are used to construct the binary numbers, that can then be operated
on by the computer's logic circuits. A similar construction is used
in the quantum computer, except that each qubit (quantum bit) can represent
BOTH 1 AND 0 at any moment, and therefore a sequence of qubits of length
n can store 2n numbers at a given moment, and allows the operation
on all of them simultaneously. In 1994, Peter Shor developed an algorithm
that used this property to allow factorization of large numbers in what
may be as little as n3 time. An functional algorithm of
that complexity is likely to make any RSA encrypted message readable within
a reasonable amount of time (as opposed to times on the order of the age
of the universe for classical computers and extremely long RSA keys).
Quantum Cryptography
So does this mean that all information in the age of quantum computing
will be freely accessible? Not quite, since although quantum computing
may theoretically be effective in breaking current cryptographic methods,
quantum physics also provides a solution that will allow for data security
methods that are immune to quantum computing attacks. Quantum cryptography
relies on the polarization of photons for its security, and can be implemented
as follows using Alice and Bob, who again wish to communicate, and the
eavesdropper Eve:
-
Alice sends Bob a stream of photons, polarized at random at either 0, 45,
90, or 135 degrees, recording the polarization of each photon.
-
Bob receives the stream, and chooses to measure the polarization along
the horizontal/vertical directions, or the diagonal directions. For
example, if he chooses to measure a photon along the horizontal/vertical
direction, he would detect a 0 or 90 degree photon accurately, but would
receive a random result if the photon was polarized at either 45 or 135
degrees. Since the act of measuring the polarization may have changed
its polarization, Bob cannot simultaneously measure the horizontal/vertical
and diagonal directions for the same photon, so he measures one at random
and expects to be wrong 50% of the time.
-
Alice and Bob then compare the axes (either horizontal/vertical or diagonal)
used to generate and measure each photon, and disregard the measurements
in which Bob chose incorrectly. What remains is a stream of polariazation
measurements. Bob and Alice agree that, for example, a 0 or 45 degree
measurement represents 1, and a 90 or 135 degree measurement represents
a 0. The stream of polarization measurements can now be converted
into a stream of binary digits. The communication in this step does
not require a secure channel, since anyone intercepting it cannot retrieve
the actual polarization from the axes.
-
Alice and Bob then choose a subset of the bits produced, and compare them.
If Eve has been eavesdropping on the photon communication, she will have
been unable to do so without altering the polarization of the photons received
by Bob (unless Eve guessed the measuring orientation perfectly for each
photon in the stream). When Bob and Alice compare their subsets,
they will discover these inconsistencies and realize there was an eavesdropper.
If their subsets were identical, the would discard those bits and use the
remainder of the stream as a one-time pad key. One time pads are
considered secure, since a given encrypted message can be decrypted to
any plaintext message of the same length depending on the key (for example,
the ciphertext ABCDE can decode to BRIAN using the key APFWI, or to MONEY
using the key LMKAS, or to any other 5 letter word using other keys).
A new key should be generated for each communication, otherwise the recovery
of the plaintext becomes a trivial matter.
Theory versus Practice
To this point we have been discussing theoretical applications of quantum
physics, and as with all theory the reality is not quite the same.
A quantum computer capable of factoring numbers does not exist, but in
April 1998 Isaac Chuang of IBM's Almaden Research Center in San Jose and
Neil Gershenfeld of MIT released the news that they had built an elementary
quantum computer using the nuclei of a carbon atom and a hydrogen atom
in a chloroform molecule as two qubits. In March of this year (2000)
Scientists at MIT and the Department of Energy's Los Alamos National Laboratory
announced the creation of a seven-qubit quantum computer within a single
drop of liquid, although they accepted that "the world [may be] still years
away from a functional quantum computer".
Quantum cryptography appears to suffers from the effects of distance
at this point, with error rates of 3% being reported by British Telecom
researchers at a communication distance of 30km, and the maximum transmission
distances for quantum key distribution of around 50km through fiber-optic
cables, and 1/2 km in full daylight. Also, securing communication
through the encryption key is of small concern if the remainder of the
implementation is vulnerable. In "Minds, Machines, and the Multiverse"
IBM's Charles Bennett admits that
"[i]t's hard for a cryptosystem
to be totally secure...[y]ou have to be aware of all sorts of possible
attacks. For example, from an eavesdropper's point of view, our quantum
cryptosystem wasn't secure at all, becasue the Pockel cells were running
from a power supply that hummed. And it hummed at different loudness
depending on the voltage applied to the cells. So although you wouldn't
be able to eavesdrop on the photons, you could just listen to the hum to
find out what data were going through the system!" (197)
Obviously neither of these technologies are completely developed or ready
for use in real-world applications. However, they both hold exciting
possibilities, and the boundaries are pushed farther forward each year.
Sources and Further Reading
Brown, Julian. Minds, Machines, and the Multiverse., (Simon &
Schuster, New York 2000).
Schneier, Bruce. Applied cryptography: protocols, algorithms,
and source code in C., (John Wiley & Sons, New York 1994).
Oxford Centre for Quantum Computation
http://www.qubit.org/
Quantum Computation/Cryptography at
Los Alamos
http://qso.lanl.gov/qc/
Scientific
American: Feature Article: Quantum Computing with Molecules: June 1998
http://www.media.mit.edu/physics/publications/papers/98.06.sciam/0698gershenfeld.html
Scientists
make seven-bit quantum leap in computer research
http://web.mit.edu/newsoffice/tt/2000/mar29/quantum.html