The quantum breakthroughs behind Google's Q-Day deadline rethink
Two new papers suggest quantum computers could crack modern encryption in minutes, accelerating fears that Q-Day may arrive sooner than expected.
Last week, Google dropped a bombshell by announcing it had moved its deadline for adoption of quantum-safe encryption forward to 2029.
Officially, Google stated that the risk of harvest now, decrypt later attacks had inspired the decision.
But a number of papers published this week are leading tech industry commentators to ask what really motivated the tech giant to accelerate its shift to post-quantum cryptography (PQC).
The first comes from Google itself. In a new whitepaper, its researchers suggest that future quantum computers may be able to break the elliptic curve cryptography underpinning cryptocurrencies in minutes, using roughly 20-fold fewer physical qubits than previously estimated.
They describe a more efficient "circuit" to achieve this feat, referring to the sequence of quantum operations used to execute Shor’s algorithm, a mathematically proven quantum algorithm that can solve the problems underlying modern encryption exponentially faster than classical methods.
Google’s quantum warning
The paper specifically considered on-spend attacks, which target transactions while they are still in transit. When a user broadcasts a transaction, an attacker would need to derive the private key before it is confirmed on the blockchain.
A quantum computer capable of solving ECDLP within the network’s settlement window could achieve this in around 400 milliseconds for Solana, 12 seconds for Ethereum and roughly 10 minutes for Bitcoin - a potentially disastrous scenario that is still very much in the realm of future threat rather than imminent cataclysm.
Google wrote: "We want to raise awareness on this issue and are providing the cryptocurrency community with recommendations to improve security and stability before this is possible, including transitioning blockchains to post-quantum cryptography (PQC), which is resistant to quantum attacks.
"To share this research responsibly, we engaged with the U.S. government and developed a new method to describe these vulnerabilities via a zero-knowledge proof, so they can be verified without providing a roadmap for bad actors. We urge other research teams to do the same to keep people safe."
After demonstrating the success of their circuit, researchers withheld details of how they optimised the algorithm, which was validated using a zero-knowledge proof - a method that proves a result is correct without revealing the underlying workings.
A second quantum signal
Another paper from researchers at Caltech and collaborators also published today points in the same direction, once again indicating that breaking elliptic curve cryptography may require significantly fewer quantum resources than earlier projections indicated.
The team found that Shor’s algorithm could be executed at cryptographically relevant scales with as few as 10,000 physical qubits in a neutral-atom quantum computing architecture, in which large arrays of atoms are trapped and controlled with lasers to enable scalable, fault-tolerant quantum computation.
This research revised previous estimates of the number of qubits needed to crack elliptic curve encryption, bringing them down from the millions, although it also advised that "substantial expertise, experimental development effort and architectural design" are needed to turn theory into reality.
On X, Bas Westerbaan, a principal research engineer at Cloudflare, focused on post-quantum, said this pair of papers represented "two puzzle pieces" indicating what may have "spooked Google into setting its post-quantum migration timeline to 2029".
"Google’s 2029 deadline starts to make a lot of sense," he wrote.
READ MORE: How can businesses address the looming risks of quantum computing?
READ MORE: When will quantum computing have its "ChatGPT moment"?
Commenting on why Google had withheld its zero-knowledge proof, he added: "The takeaway here is that we clearly moved beyond the point where all quantum progress is public."
Westerbaan also described the resource estimate of running Shor's algorithm on neutral atom architecture as "shockingly low".
However, whilst the research and Google's deadline realignment sound ominous, we still don't know when Q-Day will arrive - although it's clear businesses should start preparing as soon as possible.
Craig Gidney, one of the researchers who worked on Google's paper, tweeted: "I would bet against Q day by 2030, but I wouldn't bet against it at 10:1 odds. Approximately 10% risk is unacceptably high here, so I'm very in favor of transitioning to quantum-safe cryptography by 2029.
"Yes, this means I 90% expect to be made fun of in 2030. Oh well."
