Quantum Computing Kills Encryption
Source: Elliot Williams
Imagine a world where the most widely-used cryptographic methods turn out to be broken: quantum computers allow encrypted Internet data transactions to become readable by anyone who happened to be listening. No more HTTPS, no more PGP. It sounds a little bit sci-fi, but that’s exactly the scenario that cryptographers interested in post-quantum crypto are working to save us from. And although the (potential) threat of quantum computing to cryptography is already well-known, this summer has seen a flurry of activity in the field, so we felt it was time for a recap.
How Bad Is It?
If you take the development of serious quantum computing power as a given, all of the encryption methods based on factoring primes or doing modular exponentials, most notably RSA, elliptic curve cryptography, and Diffie-Hellman are all in trouble. Specifically, Shor’s algorithm, when applied on a quantum computer, will render the previously difficult math problems that underlie these methods trivially easy almost irrespective of chosen key length. That covers most currently used public-key crypto and the key exchange that’s used in negotiating an SSL connection. That is (or will be) bad news as those are what’s used for nearly every important encrypted transaction that touches your daily life.
crypto-quantum-computers-quoteAll is not doom and gloom, however. There are families of public-key algorithms that aren’t solved by Shor’s algorithm or any of the other known quantum algorithms, although they haven’t been subjected to as much (classical) cryptanalysis and the algorithms and protocols aren’t as polished yet. (More on this topic below.)
Strong symmetric ciphers, algorithms that use the same key for encryption and decryption (AES, Blowfish, etc.) will also be easier to crack with quantum computers, but only by roughly a factor of two. So if you are happy with AES-128 today, you’ll be happy with AES-256 in a quantum-computing future. That’s good news for a lot of the nation’s classified documents, for instance.
But let’s just reiterate that the hollowing-out of essentially all public-key crypto would be a very bad thing.
Is Quantum for Real?
Quantum computing is still in its infancy, but it may already be time to start worrying about your data today. As a warning sign, the NSA backed off of its previous recommendations because they weren’t robust to quantum computing attacks. For sheer Schadenfreude, read the following excerpt from this August update to their website:
For those vendors and partners that have already transitioned to Suite B [elliptic curve cryptography], we recognize that this took a great deal of effort on your part, and we thank you for your efforts. … Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be. Thus, we have been obligated to update our strategy.
In other words, “sorry we got you to spend lots of money switching over to something that’s now looking to be obsolete in the near future”. So the NSA is taking the quantum threat seriously.
While it’s sweet to see the NSA publicly eat a little bit of (pre-emptive) crow, the fact that they’re afraid that quantum cryptanalysis is going to break things in the near future, but they don’t have any solid recommended alternatives yet, should scare you a little bit. Indeed, on their list of recommendations, only AES is not completely destroyed by quantum computing. That’s kinda spooky. This article sparked by NSA’s revelation at Ars Technica is a good read.
How Soon?
In short, it looks like the quantum computing apocalypse is coming, but there’s current research going on and hopefully we’ll get some solid procedures in place in time. Nobody really knows how long we’ve got until quantum computers will be able to handle real-world cryptanalysis, but the numbers that the post-quantum folks toss around are in the ten-to-thirty year range.
Sometime before flying cars, then. As far as Shor’s algorithm goes, the largest quantum-computer-factored multiple-of-primes is 21. (Which two primes those are is left as an exercise to the reader.) Before laughing too hard, bear in mind that five years ago the largest possible factor was fifteen, and there’s a lot of research money and brains going into the quantum computing problem.
And when the computers arrive, they’ll have a whole spate of potential algorithms waiting for them to crunch on. The Quantum Algorithm Zoo, maintained by [Stephen Jordan], a physicist at NIST, is frequently updated and takes stock of the state of the art. Looking through the list, if you think your problem is hard but it’s in the “superpolynomial” improvement category, it probably won’t be hard forever.
What Can Be Done?
In early September, a group of crypto scientists working on post-quantum cryptography met up for a week-long seminar in a German mansion and put their heads together. This Nature article nicely summarizes the meeting, and if you’re interested in what you could be doing now to safeguard your data further than a couple decades into the future, the initial recommendations for post-quantum encryption systems that came out of the seminar summarize the state of the art.
In particular, McEliece cryptosystems come out looking like a good alternative to the current public-key infrastructure. Instead of relying on factoring large numbers, a McEliece system hides your data by first wrapping it up with an error-correcting code (ECC) and then deliberately adding noise to it. Quantum computers, incidentally, turn out not to be very useful in computing some types of ECCs, which is the whole point of this operation.
Normally ECCs make it easy to recover a signal that has noise added to it; they’re not “codes” in the encryption sense at all. The crucial step in McEliece cryptography is that you create the ECC with an easy-to-reverse code, and then convert the ECC into a hard-to-solve one by pre- and post-multiplying by matrices. These matrices, that turn the hard problem into the easy problem and vice-versa, become the secret key. So you take your data, add error correction, then add noise, and then make removing the noise difficult unless you’ve got the “password”.
If you’re interested in digging a little bit deeper into the methods of quantum computing and quantum-proof crypto, this mathy but still readable survey of the field from 2001 (PDF) is a great start.
Punchline
Practical quantum computing is probably ten to thirty years away. When it comes, whatever you’ve encrypted using today’s standard public-key encryption systems will be trivial to decrypt. Anyone storing your (or your government’s) data now will likely be able to read it when today’s toddler is enrolling in college. And you can bet that a good part of the rationale for the NSA’s recommendation about transitioning away from susceptible technologies is that they know of some large, well-funded government agencies who are doing that storing on a large scale today.
So is changing our public-key crypto today too early or too late? The tide seems to be just turning. The risk of switching right now to a quantum-proof method like McEliece is that it’s less battle-tested than RSA, and certainly slower to implement because it hasn’t yet been über-optimized, but the costs of not switching are growing year by year. It’s like Frogger, where you’re waiting for a log with a fly on it, but you’re also scrolling off the side of the screen. We’ve probably all got to jump, but when?
| }
|