Quantum computers breaking encryption? Don’t panic!

If clever engineers somehow figure out how to build large-scale quantum computers, it would make some, but not all, known public-key encryption algorithms essentially useless. But there are already public-key encryption algorithms that are known, even ones that have been through reputable standards processes, that will still be secure if this happens.

Quantum ComputersUnderlying all public-key encryption algorithms is a mathematical calculation with a particular property: that it is easy to calculate in one direction but hard to do in the other direction. There are actually precise technical definitions of “easy” and “hard,” that are probably too arcane to go into here, but the main idea behind a calculation being easy or hard is that easy calculations are practical to implement for reasonably big numbers while hard ones are not.

In cryptography, this roughly means that a calculation is easy if the time that it takes to do it can be written as a polynomial in the number of bits comprising a key and that a calculation is hard if the time that it takes to do it is either exponential or subexponential in the number of bits comprising a key. The number of bits comprising a key is about the base-two logarithm of the key itself. Changing the base of a logarithm just adds a constant factor that does not change as numbers get either bigger or smaller, so it is common practice to just use whatever base for logarithms is the most convenient when talking about encryption and to not worry about this constant factor.

So if a key is represented by the number N, then an easy calculation can be done in polynomial time in log N, and a hard calculation takes either exponential or subexponential time in log N. Most of the calculations that are commonly used to implement public-key encryption scale roughly like the cube of the number of bits comprising a key, or their running time is O(log3N).

A useful public-key encryption algorithm has the property that if you have the right public key, calculating a ciphertext value from a plaintext value is easy. It also has the property that with the right private key it is easy to recover the plaintext value from that ciphertext value, but without that private key, it is hard to do that. Because the difficulty of doing a hard calculation increases dramatically as the size of the numbers used in the calculation increases, this means that it is not too hard to use big public or private keys to perform encryption or decryption operations, without the right key that hard calculation quickly gets so expensive that it is essentially impossible to ever do.

Now suppose that we could somehow build large-scale quantum computers. One side-effect of having these computers is that they let you implement algorithms that are not possible to implement on a classical (non-quantum) computer. Some of these algorithms turn what is a hard calculation on a classical computer into an easy calculation on a quantum computer. And these calculations happen to be to very ones that are used in many of today’s public-key encryption algorithms.

So if the hard calculations that are the basis for the security of public-key encryption algorithms become easy on a quantum computer, that means that it becomes easy to do a decryption calculation without the right private key. In other words, it becomes no more difficult for an adversary to do a decryption calculation without the right private key than it was for the message to be encrypted in the first place. Because this happens to all the commonly used encryption algorithms, this means that all of the commonly used encryption algorithms will provide essentially no security in a world where quantum computers are available.

But there are calculations that stay hard, even if they are done on a quantum computer. And because it is possible to create ways to do public-key encryption with these calculations, this means that quantum computers will not end the security of all public-key encryption algorithms. It just means that it ends the security of all the ones that are commonly used today.

So there is really no reason to panic if researchers manage to find a way to create large-scale quantum computers. They almost certainly will not find a way to do this very quickly. That means that we would have plenty of time to stop using the weak algorithms and start using the strong ones. Perhaps even the ones that have already been through a reputable standards process.

About the Author
Luther Martin, Micro Focus Distinguished Technologist, is a frequent contributor to articles and blogs. Recent articles include Relax! Good encryption practices won’t affect app performance in TechBeacon Magazine, The Security of Cryptography and the Wisdom of Crowds, in the ISSA Journal, and Quantum Computing? Really? in the voltage.com blog.

Leave a Reply

Your email address will not be published. Required fields are marked *