Quantum Computers Herald a New Age of Computing Power and (GASP!) the End of Encryption as We Know It

There is far too much hyperbole out there about quantum computing’s impact on security and encryption. And that means something coming from me, cause you know I’m a homer. I get that people are alarmed, but many times the people talking about the topic have no expertise at all. They are not security specialists, and they don’t seem to know much about quantum computing. Their dark predictions appear to stem from the misguided assumption that a faster, more powerful computer means the end of encryption as we know it. That is patently false.

First, the Speed Issue

There is no doubt that quantum computers are faster than classical computers, but only at very specific–and at this point in their evolution, still emerging–tasks. At this time, no one can tell you how much faster a quantum computer is than a classical computer with any degree of accuracy. That’s one of the reasons why I’m working with the IEEE and several leading quantum computing companies to create a benchmarking standard so that we can talk about speed differences in measurable facts and not wild-a$$ guesses.

Back to Breaking the Internet Like a Kardashian

So, assuming that quantum computers will be as fast as we think they will be at some point, let’s think about the encryption problem logically. Use public key encryption for context, since it’s popular and integral to several Internet standards.  Also popular wisdom on the Internets is that it’s deader than the Dodo once real quantum computers arrive.

Let’s say I have a quantum computer and some intercepted encrypted data. I want to find your private key.  With my speedy quantum computer, my advantage is that I can brute force the identification of your key in polynomial time using Shor’s Algorithm. In this case, polynomial time means really, really fast. Bad for you, right?

Maybe not. You know that I have a quantum computer, right?  And you know I’m coming for your key.  So what do you do?  Might I suggest you simply double or triple your key length?  Researchers from the University of Illinois, Penn, and the Technische Universiteit Eindhoven (Netherlands) have proposed some tweaks to RSA (the algorithm behind most public key encryption) to harden it against quantum computers. The RSA algorithm is already slightly faster than Shor’s algorithm, and lengthening your key widens that speed gap.  Add in these tweaks, and voilà.  Public key encryption is still useful in a post-quantum computer world.

Doubling the length of the encryption key is even more effective in a symmetric encryption scheme. Quantum computers could use Grover’s Algorithm to break symmetric keys in quadratic time, but that’s not nearly fast enough to overcome a longer key. It’s easy to romanticize quantum computing. And while the technology is closer than you think, it’s not magic.  It will not be the end of encryption, as many propose.

Don’t Take it From Me

In his blog, renowned security technologist Bruce Schneier has written “There are lesser-known public-key algorithms such as McEliece and lattice-based algorithms that, while less efficient than the ones we use, are currently secure against a quantum computer.” As I type, cryptographers are designing new post-quantum algorithms. There are several forums to advance their efforts such as the PQCrypto Conference and the workshops on “Quantum Safe Cryptography” hosted by the European Telecommunications Standards Institute (ETSI) and the Institute for Quantum Computing. In the U.S., NIST, the NSA, and many other organizations began working on combating the “quantum threat” far in advance of its arrival. There are hundreds of researchers working in this well-defined area of study, called “post-quantum cryptography.”

The Future is Bright

Take a deep breath.  It’s not the end of encryption. Let’s not scare the masses with horror stories about a technology that will change our world for the better.  Why not talk about the potential for new quantum encryption schemes? Or how the power of quantum computers could be used to improve security? Every new technology can be viewed as a double-edged sword. When it comes to security, too many people are only seeing one of the edges.