We already knew the NSA was working on powerful quantum computing technology. It says so on its website. Until now, however, the scope and progress of the research has been the subject of little more than speculation. Yesterday, documents provided to the Washington Post by Edward Snowden shed more light on what the NSA wants to use it for (cracking encryption; no surprise there) and how far along they are (not very; again no surprise).
According to the documents, the NSA is looking to build “a cryptologically useful quantum computer” as part of a $79.7 million research program suggestively named “Penetrating Hard Targets.” In essence, the agency wants to use super-fast quantum computing to crack the encryption that protects most the world’s online banking transactions and other sensitive data transmitted over the Internet. The documents also suggest that, as MIT quantum computing expert Scott Aaronson told us last summer, the NSA is likely no closer to building a useful quantum computer than anybody else.
“(Quantum) cryptography is a long way from practicality, despite anything you may have read otherwise,” Aaronson said. “The only way that could not be the case is if the NSA had some gigantic crash program that was decades ahead of everyone else. I’ve talked to people at NSA and that seems very unlikely.”
So what is quantum computing?
Quantum computing differs from the computers on your lap or in your pocket, because they rely on what are known as qubits, instead of bits. Unlike bits, which process computations by switching between 0 and 1, qubits are sub-atomic particles that behave in very strange ways: they can be either 0, 1, or anything in between. This allows for computations to be done in parallel, potentially speeding up computations up to a million times faster than traditional computers. (For more, check out our interactive explainer).
Watch physicists and futurists explain quantum computing in song:
Due to the unstable nature of qubits, researchers have been unable to build a quantum computer containing enough qubits for the machine to be of any practical use. And for many types of computations, scientists aren’t even sure if quantum computers would be any more efficient than classical computers. One computation we know quantum computers can theoretically beat classical computers at, however, is finding the prime factors of really really big numbers. And it just so happens that the most common form of encryption on the Web today relies on the difficulty of factoring these giant numbers.
How quantum computing could beat encryption
In the 90s, companies began using what’s known as “public key cryptography” to protect sensitive information online. In the past, most encryption methods used private keys, meaning both sender and receiver had to share a key ahead of time. This was problematic for some transmissions because the moment a private key is shared with an individual, that creates a potential weakness in the crypto system.
Public key cryptography, however, employs two keys: one private and one public. The public key can be used by anybody to encrypt data or verify a signature, but only the verified owner of a private key can decrypt it. It works on the premise of one-way functions: math equations that are easy to solve but extremely difficult to reverse. In widely-used cryptosystems like RSA, the encryption equation involves multiplying two incredibly large prime numbers, which is easy. But the decryption equation involves working backwards to find those prime factors, an equation that’s not so easy.
At least not for a classical computer. Quantum computers would be extremely good at factoring these numbers. According to John Preskill, a theoretical physicist at Cal Tech, a 193-digit number takes months to factor using classical computers. A 500-digit number would take a classical computer the approximate age of the universe to factor. A quantum computer, however, could factor the 193-digit number in just 0.1 seconds, and the 500-digit number in just 2 seconds.
So is that it? Is the NSA on its way to achieving its goal of dismantling encryption on the Web once for all?
Maybe in its current form, but as our interactive history of encryption notes, the art of securing sensitive information has changed a lot over the past hundred years and will continue to evolve. Some forward-thinking crypto experts are now using quantum principles to protect secure data, not attack it, and they appear to be farther along than the quantum attackers.
Swiss startup ID Quantique has already inked a deal with Columbus, Ohio’s Battelle Labs to use “quantum key distribution” (QKD) to protect secure data transmitted between its offices in Central Ohio. QKD exploits the so-called “observer effect” by alerting sender and receiver if a piece of secure data has been observed or intercepted en route. It’s the first commercial QKD network in the country, and while it operates on a relatively small scale, researchers are already working on ways to expand the size of a network so it could potentially cover an entire country.
“Interestingly enough with the NSA stories, we saw a spike of interest from small governments,” Serguei Kouzmine, an investor in ID Quantique, told me in October. “They came to ID Quantique and said, ‘Hey, give us what you do.’”
It’s not hard to see how a practical quantum computer would completely break public key cryptography and thus open up much of the Web’s secure transmissions to prying eyes. Although the NSA may be decades away from accomplishing this on any meaningful scale, it’s important for security experts and cryptanalysts to keep these threats in mind as encryption continues to evolve.
Like all crypto systems, public key cryptography will work until it doesn’t. If the time comes when the NSA can easily crack it using quantum computing, Web companies need to be ready to adapt to a new system.