Google bumps up Q Day deadline to 2029, far sooner than previously thought

Google is dramatically shortening its deadline readiness for the arrival of Q Day, the point at which existing quantum computers can break public-key cryptography algorithms that secure decades’ worth of secrets belonging to militaries, banks, governments, and nearly every individual on earth.

In a post published on Wednesday, Google said it is giving itself until 2029 to prepare for this event. The post went on to warn that the rest of the world needs to follow suit by adopting PQC—short for post-quantum cryptography—algorithms to augment or replace elliptic curves and RSA, both of which will be broken.

The end is nigh

“As a pioneer in both quantum and PQC, it’s our responsibility to lead by example and share an ambitious timeline,” wrote Heather Adkins, Google’s VP of security engineering, and Sophie Schmieg, a senior cryptography engineer. “By doing this, we hope to provide the clarity and urgency needed to accelerate digital transitions not only for Google, but also across the industry.”

Estimates for when Q Day will arrive have varied widely since the mid-1990s, when mathematician Peter Shor first showed that a quantum computer of sufficient strength could factor integers in polynomial time, much faster than classical computers. That put the world on notice that RSA’s days were limited. Follow-on research showed quantum computers provided a similar speed-up in solving the discrete log problem that underpins elliptic curves.

The timeline for this arrival is based on when existing quantum computers will contain the required number of qubits that can correct inevitable errors. In 2012, most estimates were that a 2048-bit RSA key could be broken by a quantum computer with a billion physical qubits. By 2019, the estimate was lowered to 20 million physical qubits. A running joke among researchers has been that Q Day has been 20 years away for the past 30 years.

In January, Google published research that once again drastically lowered the expected threshold for breaking RSA. It showed that a 2048-bit RSA integer could be factored in less than a week with a quantum computer with 1 million “noisy qubits,” meaning qubits that are prone to errors resulting from environmental conditions that disrupt the quantum state. The research was led by Craig Gidney, the same scientist behind the 2019 estimate.

In preparation for Q Day, cryptographers have devised new encryption algorithms that rely on problems that quantum computers can’t solve. Rather than factoring the discrete log, the problems involve mathematical structures known as lattices and cryptographic hashes. The National Institute of Standards and Technology has advanced several algorithms that have yet to be broken and are presumed to be secure.

PQC algorithms have made their way into a variety of products and protocols, although largely in piecemeal fashion. Last year, the Signal messenger added ML-KEM-768, an implementation of the CRYSTALS-Kyber algorithm, to its existing encryption engine. Software and services from Google, Apple, Cloudflare, and dozens of others have also done the same.

“Quantum computers will pose a significant threat to current cryptographic standards, and specifically to encryption and digital signatures,” Google’s Wednesday morning post stated. “The threat to encryption is relevant today with store-now-decrypt-later attacks, while digital signatures are a future threat that require the transition to PQC prior to a Cryptographically Relevant Quantum Computer (CRQC). That’s why we’ve adjusted our threat model to prioritize PQC migration for authentication services—an important component of online security and digital signature migrations. We recommend that other engineering teams follow suit.”