Given the recent ubiquity of cyber-scandals—Colin Powell’s stolen e-mails, Simone Biles’s leaked medical records, half a billion plundered Yahoo accounts—you might get the impression that hackers can already break into just about any computer they want. But the situation could be a lot worse. The encryption methods that protect everything from online shopping to diplomatic communications remain effectively impregnable when properly implemented, even if, in practice, there are frequent breaches—whistle-blowers, careless clicks, and so on. This relatively happy state of affairs will not, however, endure. Scientists around the world are inching toward the development of a fully functioning quantum computer, a new type of machine that would, on its first day of operation, be capable of cracking the Internet’s most widely used codes. Precisely when that day will arrive is unclear, but it could be in as little as ten years. Experts call the countdown Y2Q: “years to quantum.”
This looming but uncertain deadline hovered in the air at the Hilton Toronto last week, where government officials, cyber-security researchers, and representatives from companies like Amazon, Microsoft, and Intel gathered for an international workshop on “quantum-safe cryptography.” Michele Mosca, a professor at the University of Waterloo’s Institute for Quantum Computing and the co-host of the workshop, pegged the odds of reaching Y2Q by 2026 at one in seven, rising to one in two by 2031. But the exact date doesn’t really matter, because the time needed to invent, battle-test, standardize, and roll out new security algorithms Internet-wide might be just as long. Brian LaMacchia, the head of security and cryptography at Microsoft Research, has a working estimate of 2030. “The people who try to build quantum computers, who sit on the floor upstairs from me, said fifteen years last year,” he told me. “So I said, O.K., let’s work backwards from that. And I’m out of time.”
Classical computers encode information as a series of bits, which can be either 0 or 1, and then manipulate those bits according to simple rules. A quantum computer isn’t just a faster or better classical computer; it’s fundamentally different. Instead of bits, it stores information as qubits, which can be 0, 1, or both at once. That’s a consequence of the quantum-mechanical property of superposition, which allows physical objects to exist in multiple states, or even be in different places, at one time. Thus, two qubits can represent four states simultaneously (00, 01, 10, 11), and a hundred qubits can represent 1.3 quadrillion quadrillion. This quantum peculiarity allows the computer to find patterns in huge data sets very quickly—to get detailed information about a forest without looking at all the trees, as Mosca put it. The main mathematical challenge in breaking current codes is factoring very large numbers, which for classical computers is the equivalent of trying combination after combination to see if it opens a lock. As the keys get longer, the locks get tougher. It took about two years on hundreds of computers to unlock a single instance of the RSA-768 algorithm, which, as its name suggests, requires a key that is seven hundred and sixty-eight bits long. Doing the same for its more secure cousin, RSA-1024, would take about a thousand times longer, and RSA-4096 is effectively out of reach. A quantum computer, on the other hand, would tackle such problems effortlessly.
When quantum computing was first proposed, in the nineteen-eighties, it was mostly a theoretical curiosity. That changed in 1994, when Peter Shor, then at A.T. & T.’s Bell Labs, demonstrated how it could apply to cryptography. Once the significance of Shor’s work became clear, the race to actually build a quantum computer became one of the hottest tickets in physics. Among the biggest players was the U.S. government, which by 2007 was spending about sixty million dollars a year on quantum-computing research. It didn’t just want to build one; it also needed to know whether anyone else was getting close. After all, top-secret messages sent today could still be embarrassing or dangerous if they were intercepted and stored, then decrypted by a device built a decade from now.
So far, the best quantum computers have just a handful of qubits—five, for example, in a system that I.B.M. announced earlier this year. The company expects to scale up to between fifty and a hundred qubits within the next decade, which would be powerful but still short of the thousand or so that LaMacchia estimates would represent a serious cryptographic threat. (D-Wave Systems, a Canadian company that caused a stir when it announced a thousand-qubit computer last year, uses an alternative approach to quantum computing that isn’t suitable for code-breaking.) This may sound like painfully modest progress after two decades, but it has been steady enough in the past few years to shift the underlying question from if to when.
The “Y2Q” handle makes explicit the parallels between the quantum threat and the Y2K bug, which, at the turn of the millennium, was supposed to make the world’s computers think it was 1900 again, bringing civilization to a grinding halt. In the popular imagination, Y2K has become a punch line, a prophecy of doom unfulfilled, like the Maya calendar turned out to be in 2012. But for many of the people at the cryptography workshop—those responsible for establishing international standards for safe computing or signing off on data-security protocols for hundred-billion-dollar companies—Y2K was a relatively minor event only because the hysteria that preceded it mobilized an estimated three hundred to five hundred billion dollars in preventive action by governments and corporations. So far, Y2Q has failed to generate quite that level of interest.
One big difference is that it was clear, if inconvenient, what needed to be done to avoid Y2K. The best way to ward off a quantum attack, on the other hand, is still very much up for debate. The simplest approach is basically mathematical: come up with new encryption algorithms that quantum computers can’t break. That doesn’t require big changes in technology, but it’s very hard to know for sure which algorithms will be resistant, until they fail. The other approach is to directly harness the weirdness of quantum mechanics; since the mere act of observing a quantum system freezes it in one state, you can construct sophisticated communications links where it’s impossible, even in theory, to eavesdrop on the message without destroying it or betraying your presence. This approach sounds great, but is far harder (and more expensive) to implement.
Both approaches have been making progress in the real world over the past few months. China, for instance, has nearly completed a twelve-hundred-mile fibre-optic “quantum backbone” that will link Shanghai and Beijing, allowing signals to travel from one end to the other without losing their quantum properties. And the world’s first quantum satellite, launched from the Gobi Desert in August, will allow the country to send fully quantum-encrypted messages over much longer distances. For most of the companies and other governments represented at the workshop, though, quantum-resistant algorithms remain the focus. In July, Google announced that it would test a candidate algorithm dubbed New Hope in a small fraction of Chrome browsers. Soon afterward, the National Institute of Standards and Technology put out a public call for input on how it should evaluate such algorithms in the future. The organization may be ready to issue standards in draft form, a NIST cryptographer at the workshop estimated, by 2022 or 2023. Some members of the crowd reacted with audible consternation.
In a sense, then, the fundamental question isn’t whether we should do something to prepare for Y2Q. It’s how we balance the seeming necessity of doing something right now with the inconvenient fact that we don’t yet know what to do. The most persuasive answer to this dilemma came from Vadim Makarov, an exuberantly bearded, Hagrid-like figure who heads the University of Waterloo’s Quantum Hacking Lab. He and his colleagues work with companies to test their quantum-cryptography systems before they go public, and have demonstrated that even “theoretically perfect” setups can be hacked when they’re actually implemented—for example, by blinding the receiving device with a bright laser that makes it unable to distinguish between quantum and classical signals. Such vulnerabilities may suggest that quantum-safe systems aren’t yet ready for prime time, but Makarov, during a panel discussion, drew the opposite conclusion. “It’s a bit of chicken-and-an-egg problem,” he said in a thick Russian accent. It will be impossible to know which systems can resist attacks until they’re out there, in the real world, inviting attacks. Waiting for a perfect solution just brings the arrival of a quantum computer closer and closer, at which point it will be too late to fix things. “So, folks, please deploy more,” Makarov said. “We want real hackers, not the toy ones like me and my students.” He smiled, not quite reassuringly.
