Google is dramatically shortening its readiness deadline 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.”
Separately, Google detailed its timeline for making Android quantum resistant, the first time the company has publicly discussed PQC support on the operating system. Starting with the beta version, Android 17 will support ML-DSA, a digital signing algorithm standard advanced by the National Institute for Standards and Technology. ML-DSA will be added to Android’s hardware root of trust. The move will allow developers to have PQC keys for signing their apps and verifying other software signatures.
Google said it now has ML-DSA integrated into the Android verified boot library, which secures the boot sequence against manipulation. Google engineers are also beginning to move remote attestation to PQC. Remote attestation is a feature that allows a device to prove its current state to a remote server to, for example, prove to a server on a corporate network that it’s running a secure OS version.
Google further said it’s adding ML-DSA support to the Android Keystore so that developers can generate ML-DSA keys and store them within the secure hardware of the device directly. Google is also planning to migrate the Play Store, and the developer signatures on every app listed in it, to PQC.
The additions are likely to put a significant workload on Android developers.
So what’s spooking Google so much?
Wednesday’s hard deadline came as a surprise to many cryptography engineers, including those who have been active in the PQC transition for years.
“That is certainly a significant acceleration/tightening of the public transition timelines we’ve seen to date, and is accelerated over even what we’ve seen the US government ask for,” Brian LaMacchia, a cryptography engineer who oversaw Microsoft’s post-quantum transition from 2015 to 2022 and now works at Farcaster Consulting Group, said in an interview. “The 2029 timeline is an aggressive speedup but raises the question of what’s motivating them.”
Google didn’t lay out the rationale for the revision in either of its posts. A spokeswoman didn’t immediately provide answers to questions sent by email.
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 10 to 20 years away for the past 30 years.
Last June, 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 don’t have an advantage over classical computers in solving. Rather than factoring or solving the discrete log, one approach involves mathematical structures known as lattices. A second approach involves a stateless hash-based digital signature scheme. The National Institute of Standards and Technology has advanced several algorithms that have yet to be broken and are presumed to be secure.
In 2022 the NSA set a deadline for PQC readiness in national security systems by 2033 and for 2030 for a few specific applications.
More recently, deadlines have been in flux as both the Biden and Trump administrations have issued executive orders prioritizing quantum readiness. Currently, the NSA is adhering to a 2031 deadline.
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.”
