Quantum Computing, the NSA, and Reality

Steve Wildstrom / January 3rd, 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.


Steve Wildstrom

Steve Wildstrom is veteran technology reporter, writer, and analyst based in the Washington, D.C. area. He created and wrote BusinessWeek’s Technology & You column for 15 years. Since leaving BusinessWeek in the fall of 2009, he has written his own blog, Wildstrom on Tech and has contributed to corporate blogs, including those of Cisco and AMD and also consults for major technology companies.
  • denardley

    Of necessity the NSA is pretty competent at keeping its work secret. That means we don’t know how far they’ve come in developing quantum computing. Edward Snowden didn’t know everything and we really can’t use his documents to estimate the NSA’s progress in that area.

    You can say three things about the NSA breaking public key encryption: (1) it’s probably one of their highest if not the highest priorities since it would let them see the secrets of those who hate us, (2) it’s reasonable to assume that at some point someone will accomplish it, and (3) if the NSA breaks public key encryption the last thing they’ll want is for *anyone* to be aware of it.

    • tz

      Off topic, but cannot resist
      “those who hate us,” is a very slippery and dangerous phrase.
      Depending on what definition you, anyone, a government, an organization, or a political party chooses to plug in to those two pronouns “those” and “us” can determine some pretty damn hideous, undesirable, undemocratic and barbaric outcomes.

  • meandyou

    All your bitcoin are belong to the NSA

Protected by Gerben Law