In view of the arrival of quantum computers, it seems that encryption methods based on factorization are nearing the end of their journey * Encryptors based on quantum encryption are based on the most advanced technologies, which is why most of the work is done in laboratories like that of MagiQ Technologies.
Gerry Sticks, Scientific American
The idea of entanglement haunted Einstein, but scientists took advantage of the phenomenon to "teleport" quantum information.
In the Thomas J. Watson IBM Research Laboratory, Charles Bennett is known as a brilliant theoretician - one of the fathers of the ever-growing field called quantum computing. Like many other theorists, Bennett did not gain much experience in the laboratory. In the physical world, he is as absent-minded as he is - he once changed the color of a teapot from green to red, after leaving it on the stove for too long. But in 1989, Bennett and his colleagues John A. Smolin and Gilles Bressard decided to ignore all the rules of caution and conducted a historic experiment that illustrated the operation of a new encryption method, based on the principles of quantum mechanics.
The team installed an experimental set-up in which photons moved in a tube 30 cm long, inside a light-tight box called "Aunt Martha's coffin". The direction in which the photons oscillated, or their polarization, represented the symbols 0 and 1 of a series of quantum bits, in short, qubits. The qubits created an encryption "key" that can be used to encrypt and decrypt a transmitter. What protected the key from prying eavesdroppers was the Heisenberg Uncertainty Principle - a fundamental principle of quantum physics, which states that measuring one property in a quantum state will disrupt the measurement of another property. In the quantum encryption method, any eavesdropper who checks the stream of photons will change them in such a way that both the sender and the receiver will notice the intrusion. In principle, this method is what is needed for the development of an encryption key that cannot be cracked.
Quantum cryptography has come a long way since that improvised project built on the desk in Bennett's office. The US National Security Agency (NSA), or one of the big banks, can now buy a quantum encryption system from one of two small companies - and there are more products on the way. This encryption method represents the first important commercial application of the field that has meanwhile been named: quantum information science, which merges quantum mechanics with information theory. The technology that will eventually emerge from this field may include a quantum computer of such power that there will be no other way to defend against its miraculous ability to crack ciphers, except one of the quantum encryption methods.
The challenge facing the cryptographers dealing with encryption today is to find a common key for the sender and receiver and make sure that no other person can obtain a copy of it. One of the most common methods of distributing secret keys for encryption and decryption is called public key cryptography. The degree of security of the public key method relies on factorization or other difficult mathematical problems. It is very easy to calculate the product of two large numbers, but it is very difficult to break them down into prime numbers. The common encryption algorithm RSA relies on factorization. The transmission is encoded using a fully visible key, for example a large number like 408,508,091 (in practice the number will be much larger). It can only be deciphered using a secret key that is in the possession of the recipient of the broadcast, which consists of two factors, say 18,313 and 22,307.
The difficulties involved in cracking existing ciphers may secure most data for ten years or more. But with the dawn of the quantum information age - and especially, in view of the presumed ability of quantum computers to perform astonishingly difficult operations of factorization - it seems that RSA and other encryption methods are nearing the end of their lives. "If the quantum computer becomes a reality, all the rules of the game will change completely," says John Rarity, a professor in the Department of Electrical and Electronics Engineering at the University of Bristol in England.
Unlike public key cryptography, quantum cryptography should remain secure when quantum computers hit the market. One of the ways to send a quantum encryption key between the sender and the receiver requires the use of a laser that emits single photons, polarized in one of two ways. In the first, the photons stand vertically or horizontally (straight mode); In the second they are tilted 45 degrees to the right or left of the vertical (oblique position). In each of the modes, the opposite positions of the photons represent binary digits of 0 or 1. The sender (cryptographers usually call her "Alice") sends out a string of bits, and randomly chooses whether the photons will be sent in a straight or diagonal position. The receiver, called "Bob" in the cryptographic parlance, makes equally random decisions regarding the situation in which he will measure the bits that reach him. Heisenberg's uncertainty principle states that he can only measure bits in one of the states, not both. Only the bits that Bob measured in the same state as Alice sent them are guaranteed to be in the correct position, and therefore retain their true value (see figure on page 80).
After the launch, Bob contacts Alice, who does not have to be confidential, to tell her which of the two modes he used to absorb each photon. But it does not reveal the value, 0 or 1, that each photon will represent. Alice tells Bob which of the situations measured correctly. Both ignore photons not observed in the correct position. The correctly measured states constitute the encryption key, which is then integrated into the algorithm that encrypts the transmission itself.
If someone listens to the traffic between Alice and Bob - let's call her "Eve" - she cannot measure the two states, thanks to Heisenberg. If she performs the measurement in the wrong position, her measurements will be wrong - even if she later sends the bits to Bob the same way she measured them. Alice and Bob will both be able to notice Eve's intrusion if they compare selected bits and check for errors.
Starting in 2003, two companies - id Quantique in Geneva and MagiQ Technologies in New York City - released commercial products that launch quantum encryption keys to distances much greater than the 30 centimeters of Bennett's experiment. The NEC company, after demonstrating a launch to a record distance of 150 km, is supposed to release its own product to the market this year. Other companies, such as IBM, Fujitsu and Toshiba are also feverishly engaged in this research. (See table on page 81).
The products on the market can send keys on single fiber optic links over distances of tens of kilometers. A system made by Magic costs $70,000 to $100,000. "A small number of customers are using the system or testing it, but it's not yet widely used on any network," comments Robert Gelfond, a former Wall Streeter who founded Magic Technologies in 1999.
Some government officials and financial institutions are afraid of receiving encrypted transmissions today and keeping them for ten years or more - by which time there will probably already be quantum computers that can crack them. Richard Hughes, who studies quantum cryptography at the Los Alamos National Laboratory, brings up other examples of information that must be kept secret for days: census data, the Coca-Cola formula or the commands of a commercial satellite. Among the expected customers for quantum encryption systems are communication providers who strive to sell their customers a secure service at the highest level.
The first attempts to include quantum encryption in active networks - and not only in point-to-point connections - have already begun. The American Defense Advanced Research Projects Agency (DARPA) funded a $4 million project to link six network nodes between Harvard University, Boston University and BBN Technologies from Cambridge, Massachusetts, which played a crucial role in establishing the Internet. The encryption keys are sent over dedicated links, and transmissions encrypted with these keys are sent over the Internet. "This is the first active quantum cryptographic network that works continuously outside the laboratory," notes Chip Elliott, project leader. The network, whose entire purpose is only to prove that the technology actually works, transmits normal and unclassified Internet transmissions. "The only secret we can imagine here is where to find parking," says Elliott. In the fall of 2004, for a continuous month, id Quantique and its partner Deckpoint from Geneva, an information service provider, demonstrated the operation of a network that allowed a set of servers in Geneva to keep a backup of their data at a site located 10 km away from them. The new keys were often distributed over a quantum-encrypted line.
The first uses of quantum encryption appear in networks with limited geographical distribution. The great advantage of the method - anyone who reads a transmission will also change it in an irreparable way - is also the reason why it is impossible to amplify the signals carrying the encryption keys using the network equipment operating today that restores weakened signals and passes them on to the next amplifier. Any use of an optical amplifier will disrupt the qubits.
The researchers who aim to increase the link range are looking beyond optical fibers, as the carriers of the quantum keys. Scientists climbed to the top of mountains - as atmospheric disturbances decrease with increasing altitude - to prove that photons can be launched through the air. One experiment at the Los Alamos National Laboratory in 2002 created a 10 km link. Another experiment was done by QinetiQ from Farnborough in England and Ludwig-Maximilians University in Munich, between two peaks in the Southern Alps, the distance between them is 23 km. Optimizing this technology - the use of larger telescopes for reception, better filters and anti-reflection coating - may allow the construction of a system that can receive and transmit signals to distances of more than 1,000 km, which is enough to reach satellites in low-Earth orbit . A network of such satellites could provide worldwide coverage. The European Space Agency is in the early stages of organizing an earth-satellite link demonstration experiment. (The European Union also launched in April a project to use quantum encryption in communication networks, which was designed in part to deal with the "Eshlon" system for intercepting and deciphering electronic communications of the US and UK intelligence services.)
In the end, the cryptographers aim to build some kind of quantum relay - in principle, a basic quantum computer that will overcome the distance limit. Such a relay will rely on the phenomenon of entanglement, which Einstein called by the famous nickname spukhafte fernwirkungen - ghostly action from afar. Anton Zeilinger and his colleagues at the Institute of Experimental Physics in Vienna took a first step towards the construction of such a relay, when they reported in the August 19, 2004 issue of the journal Nature that their group threaded a fiber optic cable through a sewer tunnel under the Danube and placed an "entangled" photon at each end. Measuring the state of polarization of one of the photons (horizontal, vertical, etc.) simultaneously dictates an identical polarization that can be measured in the other photon.
The idea of entanglement haunted Einstein, but Zeilinger and his team took advantage of the existing connection between two entwined photons to "teleport" information carried by a third photon to a distance of 600 meters, across the Danube. Such a system can be extended to a large number of relays, and the qubits of the key can be transferred across oceans and continents. In order to realize this, it will be necessary to develop exotic components such as a quantum memory that is able to store qubits without disrupting them, so that it will be possible to continue in the next link. "This whole business is still in its infancy. It has not yet come out of the physics labs," notes Nicolas Gysin, a professor at the University of Geneva who co-founded id Quantique and also conducted long-range interweaving experiments.
Perhaps the best way to install quantum memory would be using atoms, not photons. An experiment published in the October 22, 2004 issue of the journal "Science" shows how this is possible. Relying on the ideas of researchers from the University of Innsbruck in Austria, a group of researchers from the Georgia Institute of Technology wrote a paper in which they described in detail how it is possible to create an entanglement between two "clouds" of extremely cold rubidium atoms, and how it is possible to embed an identical qubit in them, thanks to the quantum link . The clouds store the qubit for longer than a photon can store. The experiment also sent the qubit value from the cloud to a photon, that is, there was a transfer of information from matter to light. Georgia-Tech's Alex Komich and Dmitri Matzukevich hope that interweaving a chain of clouds will create relays that can transmit qubits over long distances.
The immunity attributed to quantum encryption is based on a set of assumptions that do not necessarily have to exist in the real world. One of these assumptions is that only a single photon represents each qubit. When operating, quantum encryption takes a laser pulse and reduces its energy to such an extent that there is almost no chance, in the typical case, that more than one in 10 pulses will contain a photon; This is one of the reasons the transmission rate is so low. But this is only a statistical probability. In practice, a pulse may contain more than one photon. And according to the law, the eavesdropper could steal an "unnecessary" photon and use it to decipher the message. A software algorithm called "enhancing confidentiality" helps guard against this possibility by masking the values of the qubits.
Eventually the cryptographers will need better devices for sending and receiving photons. The American Standards Institute (NIST) is one of the bodies involved in the development of such standards. "One of the most interesting areas is developing detectors that can distinguish between one, two or three photons arriving at once," says NIST's Alan Migdol. The institute's researchers are also trying to deal with the problem of the low transmission speed by creating quantum keys at a rate of several megabits per second - a speed 100 times greater than what was achieved in all previous attempts, which will allow the distribution of keys even for video applications.
Quantum encryption, or indeed, any other encryption method, will still be vulnerable to attack of several types. Uninvited eavesdroppers can use various tricks to jam the receiving side's detectors and divert the qubits to an eavesdropping station. And of course, there is no way to defend against "inside work". "Cheating is the first way up [to crack ciphers]," notes Seth Lloyd, an expert in quantum computing at the Massachusetts Institute of Technology (MIT). "Quantum mechanics can't do anything against it." And yet, in the looming age of quantum information, it is possible that these new ways of keeping secrets will be superior to any other method known to cryptographers.
Quantum mechanics encrypts secrets
Alice and Bob aim to trick the eavesdropping Eve by transmitting a quantum key in the form of polarized photons, according to a method developed in the 80s by Charles Bennett and his colleagues at IBM, and now implemented in several commercial products.
1. To start generating a key, Alice sends a photon through slot 0 or 1 in a straight or diagonal polarizing filter, and records the different directions.
2. For each incoming bit, Bob randomly selects the filter slot that will be used to receive it, and records both the polarization and the bit value.
3. If the eavesdropper tries to spy on the string of photons, she may disrupt it by changing the polarization of the photons, so the transmission will not be understandable to her.
4. After all of Alice's photons have reached Bob, he informs Alice through an open communication channel - perhaps a phone or email - what was the sequence of filters that he used to receive the photons.
5. Alice informs Bob in the same conversation which filters he chose correctly. The bits that passed through the correct filters will be used by Alice and Bob to create the key with which they will encrypt and decrypt transmissions.
* Tommy Moorman; Adapted from the book Secrets of Encryption: A History of Encryptors and Decryptors from Ancient Egypt to Quantum Physics, by Simon Singh (2003).
The sellers of the immune keys
Society/Technology
id Quantique Geneva, Switzerland
A system based on optical fibers that allows quantum encryption keys to be transmitted tens of kilometers away.
MagiQ Technologies New York
A system based on optical fibers that allows quantum encryption keys to be transmitted over a distance of up to 100 km. Also includes hardware and software for transmitting broadcasts in existing networks.
NEC Tokyo
Should market a product in early 2005, after demonstrating in 2004 the transfer of keys for a record distance of 150 km.
QinetiQ Farnborough, England
Provides, under a contracting contract, systems that transfer keys through the air for distances of up to 10 km. Provided a system to BNN Technologies of Cambridge, Massachusetts.
[frame page 83]
And more on the subject
Quantum Cryptography. Charles H. Bennett, Gilles Brassard and Artur K. Ekert in Scientific American, Vol. 267, no. 4, pages 50–57; October 1992.
Secrets of encryption, Simon Singh, translation, Zohar Bar-Or, Yedioth Ahronoth, 2003.
More information about quantum encryption can be found on the websites of the companies that market it: www.idquantique.com and www.magiqtech.com
