The NSA is racing to build a quantum computer capable of cracking even the strongest encryption

The encryption battle may be leaving the realm of 1s and 0s.

The National Security Agency wants the ability to crack the strongest available encryption methods — and it’s investigating how an advanced field of computing could help.

The NSA has a $79.7 million research program called “Penetrating Hard Targets” that seeks to build “a cryptologically useful quantum computer,” according to documents leaked to the Washington Post 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.

“While obviously I can’t know for sure, that seems extraordinarily unlikely to me, and the revelations from the Snowden documents in the Washington Post article only confirm that impression,” Scott Aaronson, a professor of computer science and electrical engineering at MIT, told VentureBeat. “While many people don’t want to hear the truth, quantum computing is simply not at the stage where anyone can honestly tell you, here’s how much it will cost, here’s how long it will take, here’s how many people you’ll need, etc., and then you’ll have a scalable device.”

But either way, $80 million is hardly a realistic budget for building a scalable quantum computer today, said Aaronson.

“However, I also don’t think that $80 billion would be enough to guarantee building a quantum computer within a fixed timescale,” he added.

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 a few decades, 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 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.

Updated at 9:11 AM PT with an expanded quote from MIT professor Scott Aaronson