How Google Can Repel the Attack of the NSA Quantum Computer

Mar 17, 2014

Source:http://www.wired.com/2014/03/quantum-crypto-google

Image: D-Wave Systems, Inc.

Edward Snowden — the ex-government contractor who exposed the NSA’s efforts to spy on the web’s most popular services — offers a simple answer to this sweeping online surveillance campaign. The way to combat NSA eavesdropping, he says, is to encrypt data as it moves across the wire.

That’s what he told the tech heads at the South by Southwest conference in Austin, Texas last week, appearing by way of a video feed streamed across the net from Russia, where he’s been granted temporary asylum from the U.S. government. Properly implemented, he explained, today’s encryption techniques work: The NSA has no way of cracking them. The onus is on the tech world to actually use them. "You guys who are in the room now are all the firefighters," he said. "And we need you to help fix this."

The good news is that the giants of the net — including Google and Microsoft — are already working to encrypt data, not only as it moves across the public internet but as it travels through private lines that run between the massive data centers that underpin their many web services. According to leaked government documents, the NSA has ways of tapping these lines, opening a backdoor to the internet that even those at the heart of the tech world hadn’t thought about. If the Googles and the Microsofts encrypt the data moving between their computing facilities, they can go a long way towards answering Snowden’s call to arms.

There are other clouds on the horizon. Most notably: What happens if someone does crack current encryption techniques?

But there are other clouds on the horizon. Most notably: What happens if someone does crack current encryption techniques? That isn’t likely to happen any time soon, but in the long term, it’s a real threat — especially when you consider that researchers are slowly moving towards the creation of a quantum computer.

Based on the seemingly fantastical but very real properties of quantum mechanics — the physics of very small things — a quantum computer would have the power to instantly perform mathematical calculations that would take years with classical machines, and that could threaten today’s crypto. The NSA has funded quantum computer projects for more than a decade, and recently, leaked documents revealed that the agency is "pursuing more than just basic, unclassified research," secretly working on a quantum computer that could be a first step towards machines that could "attack high-grade public key encryption systems." If the Googles of the world are intent on protecting our data from prying eyes, they must also explore a new breed of encryption that can stand up to quantum computing.

"I wouldn’t be surprised if companies like Google are looking into this — especially given what we know about how their systems have been compromised," says Edward Frenkel, a professor of mathematics at the University of California at Berkeley whose work has spanned cryptography and quantum physics. "They really should be looking."

Fighting Fire With Fire

Odds are, Google is looking. The company declined to speak with us about the quantum threat — which is still years off, if it ever arrives at all — but the company certainly aware of it. Together with NASA, Google is now testing a machine, known as the D-Wave, that exhibits certain quantum properties. In the wake of Snowden’s revelations, it only makes sense that the company — which takes pride in far-reaching ideas — would explore the other side of this arms race.

Certainly, others are developing encryption techniques for the "post-quantum world." The most prominent example comes from a Swiss company called ID Quantique. Basically, the company wants to fight fire with fire — creating a kind of quantum encryption that can stand up to a quantum computing attack — and in some respects, its technology is much farther along than the quantum computer research they’re racing against.

The company wants to fight fire with fire. It wants to create a kind of quantum encryption that can stand up to a quantum computing attack.
Drawing on years of academic research, the company has offered a working quantum cryptography system for more than a decade. According to ID Quantique CEO Grégoire Ribordy — a former academic who helped develop the company’s technology — this is already used by banks and other organizations in Europe and the U.S. And with Snowden’s revelations in mind, he says, the company has already approached at least some of the web’s giants about using the technology to protect data as it moves between their data centers. Nothing has yet become of this, but some believe it’s a natural fit.

"This is the ideal use-case for quantum cryptography — securing information between data centers," says Vadim Makarov, a professor at the Institute of Quantum Computing in Waterloo, Canada, who has spent nearly two decades exploring quantum technologies and has worked closely with ID Quantique and its system. "The capability is already there."

id Quantique CEO. Photo: Josh Valcarcel/WIRED
ID Quantique CEO Grégoire Ribordy. Photo: Josh Valcarcel/WIRED

Photo-Crypto

Quantum cryptography is certainly a fascinating creation. It uses the unique properties of photons — particles of light — to send cryptographic keys across lines of optic fiber. With standard encryption technologies, we typically encode and decode information using a pair of digital keys: one public and one private. The problem is that a large-scale quantum computer — which would be exponentially faster than today’s classical computers — could potentially determine the private key using the public key. Doing so is just a massive integer factorization problem. But such a machine wouldn’t have an advantage against quantum keys. In theory, quantum keys are completely private, and if someone even tries to intercept them, you would know about it.

Two machines can set their keys by sending photons across an optic line, and if someone tries to read these photons, you’ll know it because the quantum properties of these tiny particles will be altered.

According to the Heisenberg Uncertainty Principle — a key tenet of quantum mechanics — if you try to measure the behavior of a quantum particle, you end up changing its behavior. This is true of photons. With the ID Quantique system, two machines can set their keys by sending photons across an optic line, and if someone tries to read these photons, you’ll know it because the quantum properties of these tiny particles will be altered. "If some third party tries to intercept the communication, they will be caught. At least, that’s the theory," says Berkeley professor Frenkel. "The question is how feasible the technology is."

One problem is that the technique doesn’t work if your fiber line is any longer than about 100 to 150 kilometers. And though Ribordy and company are working to extend this distance, they will eventually reach a theoretical distance limit — about 300 kilometers — that would still fall short of what’s needed at a company like Google, whose network now spans the globe. But, says Riboury, you can span greater distances if you string together multiple lines. The rub here is that you have to physically secure these links between lines, meaning they have to be protected in a way that you would know if someone actually located the link and broke into it.

ID Quantique is already working with a partner firm to develop such links. You can think of them as metal envelopes that would send a signal — or provide some other telltale sign — if someone poked a hole in them. This would let you securely send quantum keys across much longer distances — at least in theory. But there’s a difference between theory and reality.

Just Get a Bigger Key?

Nate Lawson, a security researcher and cryptography expert who runs a San Francisco consulting firm called SourceDNA, believes that quantum cryptography is "kind of a silly thing." In turning theory into reality, you’re forced to introduce classical techniques into the system, he says, and if you do that, you defeat the very purpose of quantum cryptography.

"It has theoretical strengths," he explains. "But in practice, you can’t build a quantum system that exists in a vacuum. You need to have it connected to other things. Computer chips that must implement the logic behind the quantum crypto, software needs to run the whole thing, and in order to just build a quantum connection, you end up building other stuff."

‘It has theoretical strengths. But in practice, you can’t build a quantum system that exists in a vacuum.’

Ribordy and others acknowledge this. But their hope is that they can locate any cracks in the system and caulk them over. At the Institute of Quantum Computing in Canada, Vadim Makarov runs a "quantum hacking" lab that seeks to do this very thing.

Lawson still isn’t convinced. But there are other ways of protecting data against the distant threat of a quantum computer. Separately from quantum cryptography, other researchers are building new types of classical encryption that take quantum attacks into account. These include a new protocol called SHA-3. Unlike public-key techniques, these methods can’t be cracked merely with a jump in computing power. But Lawson offers a much simpler option: we should just increase the length of today’s encryption keys — i.e. make them harder to crack. "The nice thing about quantum computers is that the advances are pretty slow and predictable," he says. "If ten more years pass, and quantum computers are getting closer, it’s time to increase the key size."

You can be sure the Googles of the world will consistently increase key lengths. This is a way of guarding against advances in classical computing as well. But some believe this isn’t enough, questioning whether the evolution of quantum computing is really that predictable. A breakthrough, they say, could happen at any time — especially if someone like the NSA is working behind closed doors. They believe the Googles of the world must do more. "No one knows when a quantum computer will arrive, and if it does, you could need several years to upgrade your infrastructure against attack," says Makarov. "The work on your infrastructure has to start now."