Quantum supremacy might be here, upending conventional encryption

Last week Google posted and quickly took down a report announcing a stunning quantum computing milestone. Regardless of whether the report was premature, conventional encryption’s days are numbered.

Columnist, CSO | Sep 26, 2019 3:00 am PDT

The Google universal quantum computer. — Google / Eric Lukero

Congratulations! You’re lucky to be alive during what could be the most important advance in the history of computing: the advent of quantum supremacy. Make no mistake, this event is at least as significant as the creation of the internet – and what it means is both thrilling and threatening, particularly as it relates to security.

What is quantum supremacy?

A few days ago, Fortune reported that Google, a heavy hitter in the race to make usable quantum computers, temporarily posted a research paper on a NASA website that claimed quantum supremacy. This milestone is the moment when a quantum computer finally does something that a traditional, binary, classical computer cannot – either a demonstration of unprecedented computational speed or solving a math problem that a conventional computer simply cannot solve. Google’s report seems to indicate it was a bit of both: Google’s quantum computer was able to accomplish in three minutes what the world’s fastest computer would take 10,000 years to do.

Google Bristlecone superconducting quantum processor / quantum chip.

Within hours Google retracted the report. Yes, that could mean that Google has not yet achieved quantum supremacy. But if Google hadn’t, would it have included such detail, followed by radio silence on the subject? Google, IBM and Chinese researchers have all publicly declared that quantum supremacy would arrive as early as this year. My guess is that this was an accidental release ahead of some previously discussed PR strategy.

I just finished writing a book on quantum computing and encryption called Cryptography Apocalypse, so I understand the caginess. Since 1959, when Richard Feynman talked about using the properties of quantum mechanics to foster a new computing paradigm, the world has waited for the day when quantum supremacy would occur. Now it likely has. Among other amazing things, the power of quantum computing brings the day closer when the conventional encryption we all rely on can no longer protect us.

The cryptographic break

Quantum computing’s raw computing performance for many problems isn’t that extraordinary. There are even many cases in which quantum computers are slower than traditional computers. But we do know of two particular types of problems where quantum computers excel.

One type is called unstructured searches. Due to a quantum algorithm known as Grover’s algorithm, quantum computers deliver a quadratic speedup on unstructured searches. Most relevantly, it halves the protection of symmetric keys and hashes, weakening the protective security of AES-256 to AES-128, SHA2-256 to SHA2-128, and so on. Anyone wishing to be protected against a quantum computing assault should double the key sizes of their symmetric ciphers and hashes.

The other problem where quantum computers enjoy a huge advantage is in solving equations that use very large prime numbers in mathematical formulas -- which is what most of our modern-day, public key, asymmetric algorithms are based on. In 1994, quantum physicist Peter Shor showed that these types of problems could be solved in seconds to minutes on a quantum computer. We just need enough qubits (quantum bits) to help out and today’s asymmetric ciphers and digital signature schemes will fall.

The first working quantum computer arrived in 1998, when a quantum computer with only 2 qubits was built. But even with 2 qubits, the quantum computing team proved that using Shor’s algorithm would work on any size prime number equation with the right number of stable qubits. Since then, all the quantum computer manufacturers (over 100 separate groups are working on quantum computers) have been trying to add qubits and stability (error correction) to their computers.

Are we really at quantum supremacy?

For many years, quantum researchers would publicly announce each incremental advance in qubit size (or stability) whenever it occurred. Then, last year, they stopped giving updates – while at the same time announcing that they were closed to quantum supremacy.

Suppose Google has done what no other company has done – significantly increased the stability of qubits. That means other companies will figure out how to do the same, if they haven’t already.

There is no way to get to quantum supremacy and not be significantly further down the road to creating more powerful quantum computers and then moving onto cracking much of the encryption running the world.

This means that HTTPS, TLS, WiFi, digital certificates, smartcards, FIDO authentication tokens, crypto-currencies and more are either soon to be broken or already broken. You can assume that the world’s governments have been sniffing and storing adversaries’ currently “protected” network traffic, waiting for the day when they could read the other’s secrets. Google’s quantum supremacy announcement could be a hoax or premature, but I don’t think so. Either way, companies need to start thinking seriously about their post-quantum migration plans.