The NSA is racing to build a quantum computer capable of cracking strong encryption
The National Security Agency has a $79.7 million research program called “Penetrating Hard Targets” that seeks to build “a cryptologically useful quantum computer,” according to documents leaked by former NSA contractor Edward Snowden. The agency’s goal is to break strong encryption standards like RSA, which is widely used to encrypt communications and secure financial transactions.
But there’s nothing specific about the leaked documents that suggests the NSA is any further along in its quantum computing efforts than anyone else in the science and tech communities.
“It seems improbable that the NSA could be that far ahead of the open world without anybody knowing it,” MIT professor of electrical engineering Scott Aaronson told the Washington Post, which originally reported the story.
Unlike classical computers, which run in binary 1s and 0s, quantum computers are composed of quantum bits (“qubits”), which can carry far more information. Eric Ladizinsky of D-Wave, the first (and currently only) commercial quantum computing company, explained the potential of quantum computing in a recent interview with VentureBeat:
This is not another supercomputer. It’s akin to discovering fire or electricity. The quantum computers use physical phenomenon that seems like magic. The same physical object can live out many possibilities. Here’s an example I use: Imagine you’re at the Library of Congress and surrounded by 50 million books. I put an X in one of those books. Go and find the X. It would be near impossible if you were to look at one book sequentially. You would be acting classically. That is the way that processors work today.
The trick is to talk to all of those shelves at once, and have one of those shelves raise its hand when it recognizes the X.
The minimum feasible size of a quantum computer capable of running Shor’s algorithm, which could break the strong encryption of a typical 2048-bit semiprime, is hundreds of thousands of physical qubits. But the largest quantum computer constructed so far has less than 10, suggesting that the NSA is just at very preliminary research stages. A stated project goal for fiscal 2013 was to ”Demonstrate dynamical decoupling and complete quantum control on two semiconductor qubits.”
But in twenty or thirty years time, such a powerful quantum computer may be feasible. And given how long the NSA is storing everyone’s data — particularly encrypted data — some companies have expressed a need for quantum-resistant algorithms today.
The agency itself fears the national security implications of quantum computing, which is why it’s racing to keep up with the quantum computing labs of the European Union and Swiss government. “The application of quantum technologies to encryption algorithms threatens to dramatically impact the U.S. government’s ability to both protect its communications and eavesdrop on the communications of foreign governments,” according to an internal document provided by Snowden.
The NSA believes it’s making steady progress, but that there’s little prospect of an immediate breakthrough, acccording to the Post.
The spy agency has other ways to get at encrypted data: Via back doors the companies build in to their own products at the NSA’s request, through weaknesses built into publicly known encryption standards that the NSA has influenced, and through decryption keys that the NSA has access to, which enable it to decrypt data stored by many commercial products.
A late December report in Reuters suggested that security firm RSA was paid $10 million by the NSA to distribute a flawed encryption algorithm. RSA “categorically” denied the report.Related articlesD-Wave: A multimillion-dollar sham or quantum breakthrough? (Interview)RSA ‘categorically’ denies $10M NSA deal for flawed encryption – but many questions remainNSA’s top secret hacking unit ‘TAO’ in Texas targets companies from Facebook, to YouTube, Twitter, according to new leaksThe iPhone has reportedly been fully hacked by the NSA since 2008Latest NSA revelations cast deep doubt on the security of all encrypted data