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