Quantum Computing, the NSA, and Reality

on January 3, 2014

Washington Post, 1/3/2014The Washington Post led today’s front page with a very curious choice: An article, by Steven rich and Barton Gellman, that said the National Security Agency is sponsoring research into quantum computing that, if successful, would break public key encryption. The story is odd for two reasons. First, it would be very strange is NSA were not doing this, since quantum computing is a hot area of cryptologic research and that is at the core of the NSA’S mission. Second, except for revealing a contract between the NSA and an obscure University of Maryland physical sciences  lab, the article contained essentially nothing new. In fact, if you read to the end of its fourth paragraph, it told you “the documents provided by [Edward] Snowden suggest that the NSA is no closer to success than others in the scientific community.”

To understand why this is important, you’re first going to have to put up with a brief lesson in cryptography and math. Traditional “symmetric” encryption algorithms, such as the Advanced Encryption Standard, are very efficient, but have a big problem: You must have a copy of the secret key, typically a 128- or 256-bit number (roughly 40 or 80 digits) to either encrypt or decrypt the data. This isn’t much of a problem when you are, say, encrypting the data on your own hard drive. But if secret information needs to be shared, securely transmitting the secret key has traditionally been encryption’s secret heel.

That’s the problem asymmetric, or public key, encryption was designed to solve. Data encrypted with one key can be decrypted with another and only one of the keys need be kept secret. The two keys are related by a mathematical technique with the interesting property, called a trap door, that makes it simple to compute in one direction but all but impossible to reverse. In the case of the RSA algorithm, key security depends on the fact that it is easy to multiply two large prime numbers–typically about 350 or 700 digits–together, but very hard to factor their product to find the primes. In a more abstruse technique called elliptic curve encryption, the challenge lies in solving something called the discrete logarithm problem over an elliptic curve (which I am not going to attempt to explain, though you can read about it here.)

Public key encryption has one very big drawback: It is orders of magnitude slower than symmetric techniques, making it practical only for encryption of very short messages. So, public key and symmetric encryption are used together to get both speed and convenience. For example, to protect a financial transaction on the internet, public key encryption, built into your browser or app, is used to protect a “session key.” Once the session key has been transmitted, a symmetric technique such as AES is used to protect the actual data.

What does any of this have to do with quantum computers? In 1994, a Bell Labs (now MIT) mathematician named Peter Shor developed an algorithm that could factor numbers many, many times faster than the best classical technique. The difficulty was that it relied on quantum effects and could only be carried out on a quantum computer. And while the theory of quantum computing is well understood, the machines have proven devilishly difficult to build. In 2001, an IBM Research team succeeded in using Shor’s algorithm to factor a number for the first time. Unfortunately, the problem it solved was 15=3×5. In 2012, this result was improved to 21=3×7. While these were important theoretical results, they leave us a long way from being able to factor the the 1,024-bit product of two large primes. And a variant of Shor’s algorithm that can be used to solve the discrete logarithm problem is even further from practicality.

The reason why the NSA would be interested in quantum computing is obvious, but so is the fact that the current state of the art does not pose a threat to anyone. In recent years, there have been suspicions among researchers that the NSA might have achieved a secret breakthrough that would put it well ahead f academic researchers. At least to the extent we can tell by the documents obtained by Edward Snowden, that does not appear to be the case and our current techniques of encryption are safe from at least this type of attack.