Quantum computers won’t break encryption just yet

In 1992, Americans learned that a mathematician had developed a computer program capable of breaking any existing computer encryption. Former hackers, Russian agents and the NSA all sought the code, which had the potential to destabilize governments around the world.

Fortunately, that's just the fictional plot of " Sneakers ," which pulled in more than $100 million at the box office.

Two years later, a real physicist at Bell Labs named Peter Shor developed an algorithm for quantum computers that, on a powerful device, could break encryption on everything from emails to bank transactions. It's potentially a huge problem, but quantum computers are still in their infancy.

With Google's announcement of quantum computational supremacy in November 2019, concerns about a code-breaking cataclysm have grown, with some even calling it a " quantum apocalypse ." Such a scenario isn't science fiction, but it is unlikely, in part because researchers are already hard at work developing countermeasures to quantum computers.

"Once we have a quantum computer at scale in a future world, cryptography will have to be different," says Kristin Lauter , a cryptologist at Microsoft. "We'll have to choose different systems in order to be secure."

While quantum computers will be able to outperform their classical cousins in a variety of ways, the main threat to encryption comes from Shor's algorithm because of its ability to factor numbers extremely quickly. For example, the factors of 15 (besides 1 and 15) are 3 and 5. To date, the largest integer a quantum computer using Shor's algorithm has factored is 21. Last year, a classical computer factored a number with 240 digits — a number so enormous that if you counted every atom in the universe a googol times over, you still wouldn't be close. What, then, is the threat of this seemingly humble code?

Do the math

To understand why Shor's algorithm and quantum computing pose such a threat, we need to talk about classical encryption.

Suppose Alice wants to send a secret message to Bob, and she doesn't want Eve to overhear. Alice can use public-key cryptography, which is the groundwork for securing much of the information on the internet.

A commonly used analogy shows how this works with colors. Alice and Bob each have a secret color: blue for Alice and red for Bob. Neither knows the other's secret color. They also have a shared color, yellow, which is public. Both of them mix the shared color with their own secret color: Alice gets a shade of green and Bob gets a shade of orange. Then they publicly send these mixed colors. Eve, who is eavesdropping, sees these mixed colors but can't figure out what the secret color is because mixing is easy, but unmixing is hard.

Meanwhile, Alice and Bob can combine the other person's mixed color with their private color — they both end up with the same, muddy brown. Eve remains in the dark.

Public key encryption relies on large numbers instead of colors, but the same principle holds. Just like it's easy to mix colors, it's easy to multiply numbers. But going the other direction — figuring out what colors combined to create a color, or what the factors of a number are — is hard. You can multiply enormous numbers on your web browser in seconds, but doing the reverse operation takes far longer. And it gets exponentially more difficult with more digits. Your computer can factor a 100-digit number in 17 minutes; a 200-digit number would take about 75 years.

A little math example shows why Shor's algorithm is so effective. Suppose that if n is the quantity of digits in a number, Shor's algorithm can factor that number in n ¹⁰ seconds. So a two-digit number would take 2 ¹⁰ , or 1,024 seconds. A three-digit number would take 59,049 seconds, and so on.

Now let's say you have a classical algorithm that takes 10 ⁿ seconds. A two-digit number takes 10 ² , or 100 seconds, which is faster than Shor's. But the time a classical algorithm takes grows much faster — exponentially so. If n is 20, the classical algorithm would take 10 ²⁰ seconds, which is roughly 3 trillion years. Shor's algorithm would take 20 ¹⁰ seconds, or about 320,000 years, which is long, but still millions of times faster. (Note that these numbers are just examples to illustrate the principle of an exponential speedup.)

What's to be done?

There are several good reasons not to panic just yet.

First, to implement Shor's algorithm, you need to have a quantum computer with plenty of qubits and relatively little error. Right now, Google's Sycamore computer has about 50 working qubits. Breaking 2048-bit RSA, a standard encryption scheme, would take a quantum computer with 20 million qubits 8 hour s. Most researchers estimate it will take somewhere between a decade and two decades to reach this point.

There are two main approaches to securing communications from powerful quantum computers: quantum key distribution and quantum-resistant algorithms.

Quantum key distribution, or QKD, uses principles of quantum mechanics to create a secure key. Alice and Bob know that the key is secure because intercepting the information disturbs it: That's because in quantum mechanics, even the act of observation has an effect. Jon Dowling , a physicist at Louisiana State University, playfully likens it to a wax seal that's "guarded by the ghost of Heisenberg." The downside is that QKD requires expensive new infrastructure including new satellites and new fiber optics .

On the other hand, quantum-resistant algorithms would invisibly replace current algorithmic security. Also known as post-quantum cryptography, or PQC, these algorithms would operate like current public-key encryption. But instead of factoring large numbers, which quantum computers could easily crack with Shor's algorithm, they rely on algorithms that are theoretically difficult for quantum computers to calculate.

Since 2016, the National Institute of Standards and Technology has been holding what amounts to a competition to figure out which quantum-resistant algorithms will become the new standard for public-key encryption. Submissions came from teams of researchers from universities and companies around the world, including the University of Leuven in Belgium, Intel and Yale University. In June, NIST plans to release the next round of algorithms.

One worry is that none of the quantum-resistant algorithms has been proven to be quantum-proof, and they may never be.

"Here's the worst-case scenario: You could spend billions rolling out post-quantum cryptography, and then Shor 2.0 comes along and says, 'Actually, this is hackable on a quantum computer,'" Dowling says.

Lauter acknowledges this, but points out that there's never been proof that classical encryption is secure from classical attacks. That same classical encryption, she says, isn't useless yet.

"In the meantime, it's perfectly reasonable to stick with systems that we know very well," Lauter says. "And to just up the bit lengths, so that you need a larger and larger and larger quantum computer in order to be able to successfully attack them."

In other words, for the moment, quantum encryption breaking remains a possibility, not a peril.