Quantum cryptography: Can you keep a secret? RSA is DOA.

[Matthew X]

http://www.nature.com/cgi-taf/DynaPage.taf?file=/nature/journal/v418/n6895/full/418270a_fs.html&filetype=
Quantum cryptography: Can you keep a secret?

Practical products are about to emerge from the weird world of quantum 
mechanics. Erica Klarreich finds out how quantum cryptography made it from 
the lab to the marketplace
The Enigma code machine, used by the German military during the Second 
World War, was a masterpiece of complexity. Each letter of the alphabet was 
encoded by a system of wheels that could be set in an almost endless array 
of configurations, creating a seemingly unbreakable cipher. But Enigma had 
a chink in its armour.

Messages could not be decoded unless the receiver knew which wheel settings 
the sender had used. Users exchanged this information, known as a key, at 
the beginning of the message and encoded it using another, prearranged, 
key. But security for this second key was not perfect. Enigma users changed 
it only once a day. After cracking a few messages by focusing on commonly 
used words, code-breakers could tease out the second key and decipher all 
of the day's transmissions.

More then half a century later, secret messages are still only as secure as 
the keys used to encrypt them. Sensitive data are exchanged every day, yet 
no one has developed a system that ensures that the keys to these messages 
are absolutely secure.

This may soon change. Companies are close to marketing cryptographic 
systems that use quantum mechanics to offer absolute security — guaranteed 
by the laws of physics. Devices that can securely transmit keys through 
fibre-optic cables may soon be available. And it might eventually be 
possible to transmit quantum keys using satellites, allowing users across 
the world to form secure connections.

The keys used to encrypt most messages, such as those used to exchange 
credit-card information over the Internet, are themselves encrypted before 
being sent. The schemes used to disguise keys are thought to be secure, 
because cracking them would take too long for even the fastest computers. 
The widely used RSA algorithm is one example. Anyone wanting to receive a 
message publishes two numbers, one of which is the product of two very 
large prime numbers. Senders convert their message into a series of digits, 
and perform a simple mathematical calculation on the series using the 
publicly available numbers. Messages are deciphered by reversing the 
calculation.

Prime movers
This is easy to do if you know the values of the prime numbers, which are 
not published. An eavesdropper can, in principle, work them out, but for 
big enough numbers this would take millions of years with the computing 
power available today.

The future performance of such systems depends on estimates about the speed 
of future computers, and such guesses have proved wrong is the past. In 
1977, for example, Scientific American challenged computer scientists to 
decode a message encrypted using a 129-digit number1. Ron Rivest, a 
computer scientist at the Massachusetts Institute of Technology and one of 
RSA's creators, estimated that it would take 4  1016 years to factor such a 
number. But in 1994, a team of computer scientists and amateur volunteers 
managed to decipher the message by applying 1,600 computers to the problem 
over a period of eight months2.

In the same year, computer scientist Peter Shor of AT&T Labs in Florham 
Park, New Jersey, described a new kind of threat. Shor was interested in 
quantum computers — hypothetical machines that should be able to carry out 
a large number of calculations simultaneously. He showed that if such a 
computer is ever built, it will be able to factor large numbers rapidly, 
and could quickly crack all the commonly used public key systems3.

A quantum computer or new factoring technique might not come along for 
decades. But some secrets encrypted today, such as the design of nuclear 
weapons, will still be important then. "We have to assume that any 
information encrypted today is probably being recorded by eavesdroppers in 
the hope that it will be of value 10 or 20 years into the future," says 
Richard Hughes, a physicist at Los Alamos National Laboratory in New Mexico 
who works on quantum cryptography. "If they have quantum computers, they'll 
be able to look at information encrypted today and learn useful things from 
it."

But while quantum computers remain no more than an interesting possibility, 
another quantum technology could soon be ensuring total security. In 
quantum mechanics the act of measurement changes the properties of the very 
thing being measured. This is a boon to cryptologists, because it means 
that eavesdroppers cannot listen to certain types of information without 
leaving an unmistakable disturbance.

Polarized opinion
G. RIBORDY/UNIV. GENEVA

Light work: keys encoded using polarized photons have been sent between 
Alice and Bob (top) through 67 km of fibre-optic cable under Lake Geneva.

The details of a quantum cryptography system were first described in 1984 
by theoretical physicists Gilles Brassard of the University of Montreal in 
Canada and Charles Bennett of IBM's Thomas J. Watson Research Center in 
Yorktown Heights, New York4. In their scheme, Alice sends Bob a series of 
ones and zeros, which are used to generate the key. Each 'bit' is 
represented by a photon of light with one of four possible polarizations: 
horizontal, vertical or one of the two diagonals. Alice and Bob agree that 
a horizontal polarization corresponds to a zero and a vertical polarization 
corresponds to a one, and make a similar decision for the two diagonal 
polarizations.

Quantum mechanics says that Bob can either look to see whether the photon 
is horizontally or vertically polarized, or which of the diagonal 
polarizations it has, but he cannot do both. When a photon arrives at Bob's 
end, he randomly chooses which of the two types of orientation to test for. 
If Alice has sent a vertically polarized photon and Bob makes a 
horizontal–vertical measurement, he will discover the polarization 
correctly and read off a one.

But if Bob makes a diagonal measurement, the vertical polarization of the 
photon lies exactly midway between the orientations he is looking for. The 
photon will instantly switch to one of the diagonal polarizations, each 
with the same probability, and Bob has an equal chance of recording a one 
or a zero. Bob will also get a random result if he makes a 
horizontal–vertical measurement on a diagonally polarized photon.

At the end of the transmission, Bob knows he has correctly measured the 
polarizations of about half of the photons, but doesn't know which ones. So 
Bob contacts Alice on a channel that doesn't have to be secure, and tells 
her which type of measurement he made for each photon, but not the outcome 
of those measurements. Alice tells him which measurements were correct. 
They discard the incorrectly measured photons, and keep the rest for their key.

To make sure that a third party, Eve, hasn't listened in to their original 
exchange, Alice and Bob next sacrifice a small amount of their key and 
check it over the public channel for errors. If Eve has been assessing the 
polarization of the photons somewhere between Alice and Bob, she will have 
changed the polarization of about half of them. This makes about one in 
every four entries in Bob's key different from those that Alice sent — a 
clear indication that Eve has been snooping. And there is no way consistent 
with the laws of physics for Eve to cover her tracks.

In reality, noise in the channel through which the photons pass introduces 
a small number of errors into the transmission. So a clever eavesdropper 
could gain some information about the key by measuring such a small number 
of photons that Alice and Bob cannot distinguish the errors this introduces 
from those caused by noise. Alice's single-photon generator could also 
cause problems by occasionally sending out two photons instead of one. Eve 
can divert and measure one of the photons, while allowing the other to 
proceed to Bob. But in each case, Bob and Alice can generate a new key by 
applying an algorithm to their existing key. Eve, who is missing the bulk 
of the original key, cannot hope to predict the outcome of this algorithm.


Gilles Brassard (left) and Charles Bennett laid the foundations of quantum 
cryptography.

In 1989, a team led by Bennett and Brassard built a working device, and 
sent photons through the air to a receiver about 30 centimetres away5. By 
the mid-1990s, other groups were sending encrypted keys through tens of 
kilometres of optical fibre. And over the past few years, the first steps 
towards commercializing such systems have been taken. "Quantum cryptography 
is very much a reality," says Brassard.

Gone in a flash
Last October, a group of physicists at the University of Geneva in 
Switzerland launched a company called id Quantique, which will supply a 
system integrating the cryptography hardware — photon sources and 
detectors, and fibre-optic connections — needed to exchange keys. In March 
this year, they used the system to send single photons through 67-km 
telecommunication cables running under Lake Geneva6. "The system is very 
stable, and has the potential to be very fast," says Nicolas Gisin, a 
member of the team.

MagiQ Technologies, a New York firm that specializes in quantum 
technologies, is trying to a build a system in which the discussion about 
which photons have been received correctly is streamlined and integrated 
with the photon generators, detectors and fibre-optics. The firm hopes to 
market a full quantum-cryptography system by early next year.

MagiQ and id Quantique's systems are designed to connect users who are 
linked by a single dedicated fibre, but other groups are working on systems 
that can support a network of users. Last September, BBN Technologies, an 
information-technology company based in Cambridge, Massachusetts, began a 
five-year collaboration with teams at Boston and Harvard universities to 
build a quantum network connecting the three institutions. Photons will be 
routed round the network using mirrors. "The mirrors send the photon along 
without measuring it, so they don't create the kind of disturbance an 
eavesdropper would," explains Chip Elliott, an engineer at BBN.

Working devices may soon be on the market, but that does not mean that the 
engineers involved can rest on their laurels. Reliable single-photon 
generators, for example, are not yet commercially available. Today's 
systems, such as those developed by id Quantique, instead use lasers that 
generate pulses so weak that they almost never contain more than one 
photon. But at such low intensities, nine out ten attempts to fire a photon 
fail.

Current photon detectors also present some problems. To spot a single 
photon, the detectors must be so sensitive that they will sometimes 
register photons that are not there. Even then, they will typically miss 
90% of the transmitted photons. What's more, many photons are absorbed by 
the optical fibre and never make it to the receiver. "We send five million 
bits per second, but by the time we get done with all the detectors and the 
specialized protocols that shorten the key during the public discussion, we 
get somewhere between 100 and 1,000 bits per second," says Elliott.

But this is enough for cryptographic uses. The Advanced Encryption 
Standard, the encryption algorithm used by the US government, uses a key 
with a maximum of 256 bits. A key distribution that sends 500 bits per 
second would allow users to change the key roughly twice per second, more 
than ample for most purposes.

The distance that the key can be transmitted is a more important technical 
limitation. Most experts agree that the Geneva group's 67-km transmission 
is close to the maximum that can be achieved with current technology. 
Beyond about 80 km of cable, too few photons make it from Alice to Bob. 
Both id Quantique and MagiQ are reluctant to discuss who is interested in 
their products, but this limitation means that the first users are likely 
to be organizations that want to transfer highly secret material within a 
single city, such as government offices, banks and businesses.

Long-range forecast
The range could be extended by devices that strengthen the signal as it 
passes by, like those used to send telephone conversations over long 
distances. But unlike telephone repeaters, quantum versions would have to 
bolster the signal without measuring the photons. "A repeater that doesn't 
measure was thought to be impossible in the early 1980s, but since then 
scientists have shown that it is feasible in principle," Brassard says. 
"But we're nowhere near the technology to build one."

Satellites could provide an alternative means of achieving long-distance 
transmission. Hughes' team at Los Alamos is developing a key-distribution 
system that sends single photons through open air. So that the photons can 
be distinguished from all the others bombarding the detector, the team uses 
various techniques to filter the incoming light. The detector only accepts 
photons within a narrow range of wavelengths — about 0.1 nanometres — and 
ignores photons that arrive from angles outside a window of about a 
hundredth of a degree. A bright pulse of light is also sent 100 nanoseconds 
ahead of each photon, cueing the detector to expect the next signal.

LANL

In the air: Richard Hughes has sent a photon-encrypted code from a laser 
source (circled, inset) to a receiver.

"When we threw in these three filters, we could get the amount of light 
down to the level where we could detect the photons we wanted, even if the 
Sun was shining directly on the receiver," says Hughes. In a paper 
published this month7, Hughes and his colleagues describe how they sent 
keys over a distance of 10 km with rates similar to those achieved using 
optical fibres.

Ten kilometres is still a long way short of the hundreds of kilometres 
between the Earth's surface and satellites. But because air turbulence, the 
factor that most disrupts the photons, occurs predominately in the lower 
two kilometres of the atmosphere, Hughes believes his system should be able 
to send signals to satellites. "I don't see any showstoppers at all to 
doing this from ground to satellite," he says. The team is now trying to 
make the receiver light and sturdy enough to fit in a satellite and survive 
a rocket launch.

Combined with optical fibres, satellites could eventually form part of a 
long-distance transmission system. In the shorter term, the technology 
might help to protect the security of satellite television broadcasts. In 
one embarrassing breach, a hacker known as Captain Midnight interrupted a 
1986 broadcast by US company Home Box Office and sent over half of the 
company's customers a five-minute broadcast of a message complaining about 
the firm's new subscription charges.

Quantum cryptography may soon be helping to prevent similar lapses, and to 
protect sensitive transmissions. Within the next few months, such systems 
could start encrypting some of the most valuable secrets of government and 
industry. Cryptography is about to lose its Achilles' heel.

http://www.idquantique.com

http://www.magiqtech.com

http://www.bbn.com
ERICA KLARREICH
Erica Klarreich is journalist in residence at the Mathematical Sciences 
Research Institute in California.
References 1. Gardner, M. Sci. Am. 237, 120-124 (1977). | ISI |
2. Atkins, D., Graff, M., Lenstra, A. K. & Leyland, P. C. in Advances in 
Cryptology -- ASIACRYPT '94 (eds Pieprzyk, J. & Safavi-Naini, R.) 263-277 
(Springer, Heidelberg, 1995).
3. Shor, P. W. in Proc. 35th Annu. Symp Foundations Comp. Sci. (ed. 
Goldwasser, S.) 124-134 (IEEE Computer Society Press, Los Alamitos, 
California, 1994).
4. Bennett, C. H. & Brassard, G. in Proc. IEEE Int. Conference on 
Computers, Systems & Signal Processing 175-179 (IEEE Press, Los Alamitos, 
California, 1984).
5. Bennett, C. H., Bessette, F., Brassard, G., Salvail, L. & Smolin, J. J. 
Cryptol. 5, 3-28 (1992).
6. Stucki, D., Gisin, N., Guinnard, O., Ribordy, G. & Zbinden, H. New J. 
Phys. 4, 41 (2002). | Article |
7. Hughes, R. J., Nordholt, J. E., Derkacs, D. & Peterson, C. G. New J. 
Phys. 4, 43 (2002). | Article |
FROM NATURE,REG REQUIRED.