Author: Tim Folger

One bright October afternoon on a beach in San Juan, Puerto Rico, two scientists found the solution to a problem that didn’t yet exist. It was 1979. Gilles Brassard, then a newly graduated Ph.D. from Cornell University, was immersed in the warm Caribbean water when someone swam toward him. The dark-haired stranger launched into a pitch about how to make a currency that could not be counterfeited. The scheme, invented several years earlier by a Columbia University graduate student named Stephen Wiesner, involved embedding photons—particles of light—in banknotes. By the laws of quantum mechanics, any attempt to measure or copy the photons would instantaneously change their properties. Each bill would have its own string of photons, a quantum serial number that could never be duplicated. “I was surprised, of course,” says Brassard, now a professor of information science at the University of Montreal, “but I listened politely.” The conversation, he says, turned out to be a life-changing experience. His new acquaintance was Charles Bennett, a research physicist at IBM. Bennett had recognized Brassard from a conference they were attending. Although they were both intrigued by the quantum-banknote idea, they knew it was technically infeasible. Even today no one knows how to capture, immobilize and store photons in a piece of paper. Light particles, after all, tend to move rather quickly. “We’re better now but still nowhere close to anything that would be remotely practical for quantum banknotes,” Brassard says. “But it was a starting point as a thought experiment. It’s a beautiful example of an idea that is completely ridiculous in terms of being practical but at the same time turns out to be totally seminal. Because it was from there that Bennett and I had the idea for what is now known as quantum-key distribution.” Quantum-key distribution, or QKD, is a technique to encode and transmit data using photons. In principle, it provides a completely unbreakable form of cryptography. After that day on the beach, Bennett and Brassard began a five-year collaboration that produced the first cryptographic method in history to rely not on mathematical complexity but on the laws of physics. When Bennett and Brassard finally published their work in 1984, few researchers took the idea seriously or even noticed it. “It was considered a fringe pursuit,” Brassard says. “And that was for those who paid any attention. I don’t think we took ourselves very seriously either.” That is no longer the case. Thirty years ago hardly anyone outside of government intelligence agencies used cryptographic technology. Now it has become essential to routine transactions on the Internet. Whenever someone enters a password or credit-card number online, sophisticated programs built into all Web browsers work behind the scenes to keep that information safe from cyberthieves. “This is a technology that everyone needs but that no one is aware of,” says Vadim Makarov, a researcher at the Institute for Quantum Computing at the University of Waterloo in Ontario. “It just works.” But it might not work for much longer. Nearly every encryption scheme now in use is likely to become obsolete with the advent of quantum computers—machines capable of cracking the elaborate codes that protect everything from Amazon purchases to power grids. Although no one has yet built a full-blown quantum computer, researchers in academic, corporate and government laboratories around the world are trying. Among the documents released by whistle-blower Edward Snowden was a description of a secret National Security Agency project called Penetrating Hard Targets—a $79.7-million effort to build a quantum computer. “It’s hard to say with any confidence that one won’t exist in 10 or 15 years,” says Ray Newell, a physicist at Los Alamos National Laboratory. If or when that first quantum computer boots up, the most effective counter to its code-breaking powers may turn out to be another kind of quantum wizardry: cryptographic networking technology based on the theory Bennett and Brassard devised 32 years ago. Quantum encryption—a method of encoding transmissions that exploits the strange properties of single particles of light—has, it turns out, been an easier problem than building a quantum computer. Indeed, some small quantum-encryption projects are already up and running. There is just one problem: replacing the world’s encryption systems with quantum versions will probably take longer than developing quantum computers. “If you think this problem might exist in 10 to 15 years, we need to be doing this yesterday,” Newell says. “We’re probably already too late.”

VERY BIG NUMBERS Hidden behind the effortless mouse clicks and screen taps of Web commerce stands an elegant and complex mathematical scaffolding of two distinct forms of cryptography: symmetric encryption, in which the same secret key is used to encrypt and decrypt data, and asymmetric encryption, in which one key encodes the message and a different key deciphers it. Every exchange of secure information on the Internet requires both methods. A typical session between someone’s home computer and an online retailer’s Web server starts with the creation of a symmetric key that the customer and merchant will share over the Internet to encode credit-card numbers and other private information. A key is essentially a set of instructions for how to encode information. A ridiculously simple key might specify that every digit in a credit-card number be multiplied by three. In the real world, of course, keys are far more complex mathematically. Whenever someone purchases something on the Internet, the Web browser on the home computer exchanges a key with the server of the online retailer. But how is the key itself kept private during that initial exchange? A second layer of security—an asymmetric one—encrypts the symmetric key. Invented independently in the 1970s by the British secret service and academic researchers, asymmetric encryption uses two different keys: a public key and a private key. Both are necessary for any encrypted transaction. During an online purchase, a merchant’s server sends its public key to a customer’s computer. The customer’s computer then uses the merchant’s public key—which is openly available to all customers—to encrypt a shared symmetric key. After receiving the encrypted symmetric key from a customer, the merchant’s server decrypts it with a private key, which no one else possesses. Once the symmetric key is safely shared, it encrypts the rest of the transaction. The public and private keys used in asymmetric encryption are derived from the factors of very large numbers—specifically, prime numbers, integers divisible only by 1 and themselves. The public key consists of a number generated by multiplying two large prime numbers together; the private key comprises the two prime factors that create the public key. Even children can multiply two primes, but the reverse operation—splitting a large number into two primes—taxes even the most powerful computers. The numbers used in asymmetric encryption are typically hundreds of digits long. Finding the prime factors of such a large number is like trying to unmix the colors in a can of paint, Newell says: “Mixing paint is trivial. Separating paint isn’t.” The most widely used asymmetric encryption method is known as RSA, after its creators: Ron Rivest, Adi Shamir and Leonard Adleman, who developed the idea in the late 1970s at the Massachusetts Institute of Technology. Key lengths have been increasing steadily to keep them safe from hackers with faster computers and better skills; longer keys require more computing power to break. Asymmetric keys now are typically 1,024 bits long, but even leaving aside the prospect of quantum computers, that might not be enough to foil future cyberattacks. “The National Institute of Standards and Technology is actively recommending that RSA key sizes be upgraded to 2,048 bits,” says Richard Hughes, a physicist at Los Alamos. “But the increase in key size comes at a performance cost. That annoying time lag when you click ‘purchase’ and things hang for a moment or two—that’s the public-key cryptography working. And the bigger the key size, the longer the time delay.” The problem is that the processors in our computers are not improving quickly enough to keep up with the decrypting algorithms that are driving the need for increasingly long keys. “That gets to be a concern for a lot of reasons,” Hughes says. “If you’re running a cloud system with many public-key sessions at once or if you’re running something like the electric grid, you just can’t have that kind of time lag.” Even NIST’s recommended upgrade will become obsolete if quantum computers come on the scene. “I think there’s a one-in-two chance that a quantum computer will be able to break RSA-2048 by 2030,” says Michele Mosca, co-founder of the Institute for Quantum Computing, in reference to RSA’s forthcoming 2,048-bit keys. “We’ve certainly seen a lot of advances in the past five years that lead us to think we need to be prepared in case we do see quantum computers,” says Donna Dodson, chief cybersecurity adviser for NIST. “We’re of the mind-set that they’re probable.”

OF CODES AND QUBITS Why would a quantum computer be so powerful? In a conventional computer, any single bit of information can assume only one of two values: 0 or 1. A quantum computer, however, takes advantage of a weird property of the subatomic world, where individual particles can exist in many states at once. Like Erwin Schrödinger’s cat in a box—existing both alive and dead until someone opens the box for a look—a quantum bit, or qubit, of information can be a 1 and a 0 at the same time. (Physically, a qubit might be a single electron held in two spin states simultaneously.) A quantum computer with 1,000 qubits would contain 21,000 different possible quantum states, exceeding by far the total number of particles in the universe. That does not mean a quantum computer could store limitless amounts of data: any attempt to observe the qubits would immediately cause them to assume a single 1,000-bit value. Yet with clever programming, the vast number of possible qubit states could be harnessed while unobserved to perform calculations that are impossible with conventional computers. In 1994 Peter Shor, a mathematician then at AT&T Bell Laboratories, proved that a quantum computer could factor the kinds of large numbers that are used in RSA encryption—the asymmetric encoding scheme that protects the exchange of symmetric keys during Internet transactions. In effect, Shor wrote the first program for a quantum computer. Unlike a normal computer, where calculations proceed sequentially, one step at a time, a quantum computer performs all its operations simultaneously, a property Shor exploited. “Shor’s algorithm would shatter RSA,” Mosca says. But symmetric encryption methods—the most common being the Advanced Encryption Standard (AES), approved by NIST in 2001—would still be safe from quantum computers. That is because symmetric encryption programs such as AES do not use prime numbers to encode keys. Instead symmetric keys consist of randomly generated strings of 0s and 1s, typically 128 bits long. That makes for 2128 different possible key choices, which means a hacker would have to sort through some billion billion billion billion key combinations. The world’s fastest computer—China’s Tianhe-2, which can blaze through 33.8 quadrillion calculations per second—would need more than a trillion years to search all the key options. Even a quantum computer would not help hackers directly crack such huge numbers. But again, those enormous symmetric keys are encrypted during Internet transactions with asymmetric programs such as RSA, which are vulnerable to Shor’s factoring method. Before Shor’s program can dismantle RSA, though, it first needs a quantum computer of sufficient power on which to run. Within the next year Mosca predicts that a number of labs around the world will have developed rudimentary systems consisting of a few tens of qubits. “If you’re trying to factor a 2,048-bit RSA key,” he says, “you probably need at least 2,000 qubits.” The leap from tens of qubits to thousands might take a decade, but he sees no insurmountable obstacles. “Right now we meet most of the performance criteria to build a large-scale quantum computer,” he says, “just not necessarily in the same place at the same time in a system that can be made larger.”

QUANTUM NETWORKING The good news is that so far progress in quantum-encryption technology has outstripped efforts to build a working quantum computer. Quantum encryption began to take off in 1991, when Artur Ekert, a physicist at the University of Oxford, published a paper on quantum cryptography in the prestigious Physical Review Letters. Ekert, who at the time was unaware of the earlier work by Bennett and Brassard, described an alternative method of using quantum mechanics to encrypt information. His work eventually brought new recognition to Bennett and Brassard’s idea, which turned out to be more practical than Ekert’s own scheme. It was not until the early 2000s, however, that quantum-encryption technology began to move out of the lab and into the commercial world. By then, physicists had found ways to cool photon detectors—the essential and most expensive component of any quantum-encryption device—using electric currents instead of liquid nitrogen. “When I started my Ph.D. in 1997, you cooled them by dipping the detectors into a dewar of liquid nitrogen, which is okay in the lab but not very practical if you want to use them in a data center,” says Grégoire Ribordy, CEO of ID Quantique, a Swiss firm that in 2007 developed one of the first commercial quantum-encryption systems, which the Swiss government bought to protect data centers. The company has since sold its wares to Swiss banks and is now working with Battelle Memorial Institute in Columbus, Ohio, to build a network that will eventually link the company’s Ohio offices with a branch in Washington, D.C. On an overcast summer day Nino Walenta, a physicist at Battelle, shows me one of the encryption devices. “All we need is on this shelf,” he says. “All the quantum optics, and everything we need to generate keys and distribute them, is right here.” Walenta is standing next to a two-meter-high cabinet in a basement lab at Battelle’s Columbus facility. On one shelf of the cabinet is a metal box about the size of a large briefcase. Within it lies the physical realization of the quantum-coding scheme first proposed by Bennett and Brassard more than three decades ago. The hardware consists of a small laser diode, similar to those used in DVD players and bar-code scanners, that aims pulses of light at a glass filter. The filter absorbs nearly all the photons, allowing, on average, the passage of only a single particle of light at a time. Those individual photons are then polarized in one of two directions, each direction corresponding to a bit value of 1 or 0. Once filtered and polarized, the photons become the basis for a secret key that is then transmitted along a fiber-optic cable to the intended recipient, whose own hardware decodes the key by measuring the photons’ polarizations.