Quantum Computing: The Looming Threat of Quantum Decryption

Every portion of a home relies on a solid foundation. If that foundation fails, then everything above it could also be compromised. Many systems work this way: There are one or more critical elements that act as their foundations, and if those foundations fail, then the systems collapse. Much of modern life has one such foundation: data encryption. Should data encryption fail, the results would be disastrous to government, banking, e-commerce, cryptocurrencies and so forth.

Quantum computing looms in our future like a technological earthquake, because quantum decryption threatens to compromise a foundational element of data encryption schemes. This post explores quantum decryption in more detail. Future posts will explore how decision-makers are reacting to the threat, as well as potential solutions to the problem.

An earlier post generally explains quantum computing, the rapidly developing field that represents a giant step forward in our computing capabilities. It is unlikely that quantum computers will appear on our desktop any time soon, however, because while they are very good at solving certain very hard problems, they are not well-built to run the applications with which we are most familiar (e.g., web browsers). One of the very hard problems at which quantum computers excel is decrypting data.

Encrypted data is everywhere because transmitting and storing sensitive data becomes less risky when it is encrypted. If a digital eavesdropper intercepts a message in-transit or a hacker downloads a database, the risk that they can read anything meaningful is reduced when that data is encrypted.

Anything that can be encrypted can be decrypted (otherwise, what use is it?), but the question is always how difficult it is to decrypt the data. If the recipient of an encrypted message has the cryptographic key to read it, then the decryption is easy. If the eavesdropper does not have that key, then cryptography attempts to make the task of decryption as hard as possible so the eavesdropper will give up (and probably go look somewhere else).

To make the decryption task hard, researchers often turn to hard math problems. This approach makes sense: If a math problem is hard to solve, then you can incorporate it into an encryption scheme so the decryption will likewise be hard.

That works only so well because computers happen to be excellent at math. As computers became faster and faster over time, the difficulty of these underlying math problems had to grow along with them. If you explore the history of encryption, you will find moments when "X-bit encryption" schemes fell to then-current computers. In 1997, a 40-bit encryption scheme was cracked in hours; in 1998, a 56-bit DES encryption scheme was cracked in less than 3 days. Today, web browsers typically use 128- or 256-bit encryption schemes.

One of the primary "very hard math problems" in modern cryptography is prime-number factorization. Prime numbers are those that can be divided evenly only by 1 and themselves (e.g., 2, 3, 5, 7, etc.). Prime numbers can be very large (e.g., 370,248,451 and 6,643,838,879), and while multiplying two very large prime numbers together is easy enough, figuring out which two prime numbers created the result is exceedingly difficult. For example,

370,248,451 * 6,643,838,879 = 2,459,871,053,643,326,429

Calculating this product is easy (at least for a computer). Determining which two prime numbers need to be multiplied together to make 2,459,871,053,643,326,429 is very, very hard. Putting some shortcuts aside (e.g., do not waste your time with low prime numbers, such as 2 and 3), a computer needs to try multiplying all pairs of prime numbers until it reaches this huge number. Because there are a lot of prime numbers, it could take an even very fast computer centuries to complete the task. Hackers do not have centuries to wait, so they give up and move on.

The fact that prime-number factorization is very, very hard is foundational to modern encryption schemes. For example, the RSA algorithm relies on prime-number factorization. And the RSA algorithm is widely used to protect banking, telecommunications and e-commerce.

As shown by Shor's Algorithm, the looming threat is that quantum computers should be able to perform prime-number factorization at a much faster rate than today's best computers. While employing Shor's Algorithm at scale is still perhaps years away, it was experimentally shown to work in 2001. In the experiment, a quantum computer factored 15 into its constituent primes: 3 and 5. As a result, sufficiently powerful quantum computers in the future are expected to decrypt modern encryption schemes with relative ease. In short, while the hardware is not yet ready, the method to compromise modern encryption schemes is already known.

While an important foundation of modern encryption schemes is at risk, there is hope. Governments and researchers are preparing for a "post-quantum" world by exploring so-called "quantum-resilient" encryption schemes. And, ironically enough, the same science that enables quantum computing promises a new encryption scheme that is impervious to eavesdropping. Future posts will address these fascinating topics.