Post-Quantum Cryptography: The 2029 Deadline and What It Means for Internet Security
~8 min read
DevOpspost-quantum-cryptographyquantum-computingcloudflarepkitlsandroid-securitycryptography
The timeline for quantum computers breaking public-key cryptography has abruptly shifted. In April 2026, Google announced a dramatic improvement to the quantum algorithm capable of breaking elliptic curve cryptography — without revealing the algorithm itself, instead providing a zero-knowledge proof of its existence. The same week, Oratomic published resource estimates showing that breaking P-256 (the elliptic curve securing most of the web) requires only 10,000 qubits on a neutral-atom architecture.
These independent breakthroughs converged to pull the estimated Q-Day timeline from "2035+" down to somewhere between 2029 and the early 2030s. Cloudflare responded by accelerating its internal target for full post-quantum security to 2029. Google moved its own migration timeline to the same year. Bruce Schneier called the move sensible "not because I think we will have a useful quantum computer anywhere near that year, but because crypto-agility is always a good thing."
The implications for anyone operating internet infrastructure are immediate: the migration to post-quantum cryptography is no longer a speculative future project but a hard deadline with a single-digit year countdown.
Why the Timeline Collapsed
Quantum computing progress is notoriously difficult to predict because it depends on three independent engineering fronts: hardware, error correction, and algorithm design. Progress on any one front compounds the others. What made April 2026 a watershed moment was simultaneous breakthroughs on all three.
Hardware. Multiple qubit modalities are being pursued in parallel: superconducting (Google, IBM), ion-trap (Quantinuum, IonQ), neutral-atom (Atom Computing, Oratomic), and photonics (Xanadu, PsiQuantum). A few years ago, all of them had long lists of open engineering challenges. Today, most have made substantial progress. Neutral atoms in particular surprised the field with better scalability than expected, achieving what Scott Aaronson described as "detailed estimates of how many physical qubits and gates it will take to break actually deployed cryptosystems."
Error correction. All current quantum computers are noisy. They require error-correcting codes that add significant overhead — roughly 1,000 physical qubits per logical qubit for superconducting architectures. What Oratomic revealed is that neutral-atom machines, with their "reconfigurable qubits" that can be physically moved and reconnected mid-computation, allow dramatically more efficient codes. Their estimate: only 3-4 physical qubits per logical qubit for neutral-atom architectures.
Algorithm improvements. Google's undisclosed quantum algorithm massively reduces the computational cost of breaking P-256. Combined with Oratomic's architecture-specific optimizations for reconfigurable qubits, the attack surface has narrowed far faster than most expected.
The convergence is stark. In 2025, neutral atoms proved more scalable than anticipated. Now, error correction on those architectures is an order of magnitude more efficient than assumed, and the algorithms themselves require fewer qubits. The result is that a cryptographically relevant quantum computer (CRQC) is no longer a distant hypothetical.
The Authentication Problem
The industry's initial focus on post-quantum cryptography centred on encryption — preventing "harvest now, decrypt later" attacks where adversaries store encrypted traffic today to decrypt it once quantum computers arrive. Cloudflare has been mitigating this since 2022, and over 65% of human traffic to Cloudflare is already post-quantum encrypted.
What the accelerated timeline changes is the priority of authentication. If Q-Day is imminent, the immediate threat is not attackers decrypting old data but attackers walking through the front door with forged credentials.
Post-quantum authentication means upgrading digital signatures: TLS certificates, code-signing certs, API authentication keys, software update signing. Every system that relies on ECDSA or RSA signatures becomes vulnerable the day a CRQC comes online. Attackers with a quantum computer can forge a valid certificate for any domain, sign malicious software updates that devices will accept as genuine, or mint API tokens with arbitrary permissions.
As Cloudflare's analysis puts it: "An active quantum attacker has it easy — they only need to find one trusted quantum-vulnerable key to get in."
The order of priority flips. Long-lived keys — root certificates, code-signing keys, infrastructure SSH host keys — are the most urgent because they unlock the largest attack surface and are hardest to rotate. But even short-lived session authentication must migrate, because a fast CRQC could crack keys quickly enough to be dangerous in real time.
The Downgrade Problem
Adding support for post-quantum cryptography is not enough. Systems must eventually disable support for quantum-vulnerable cryptography to prevent downgrade attacks. This is trivial for a single application but nearly impossible for the web as a whole: not every browser will support post-quantum certificates overnight, and servers must keep supporting legacy clients during the transition.
The solution is hybrid schemes that combine classical and post-quantum algorithms so that both must be broken. Google's Android 17 implementation, discussed below, uses this approach for app signing.
Android 17: Post-Quantum Security in Production
Google's Android team demonstrated what a production post-quantum migration looks like with Android 17, which begins integrating NIST-standardized PQC algorithms directly into the platform. This serves as a reference architecture for anyone planning their own migration.
The deployment operates at three layers:
1. Boot Chain Integrity
Android Verified Boot (AVB) now integrates ML-DSA (Module-Lattice-Based Digital Signature Algorithm, FIPS 204), providing quantum-resistant signatures for the boot sequence. Without this, a quantum attacker could forge a boot image signature and install a persistent, undetectable rootkit.
Remote attestation — the mechanism by which a device proves its integrity to relying parties — also migrates to a fully PQC-compliant architecture, using quantum-resistant key material in the KeyMint hardware abstraction layer.
2. Application-Level Cryptography
Android Keystore natively supports ML-DSA-65 and ML-DSA-87, enabling applications to generate and verify quantum-safe signatures entirely within secure hardware (TEE). This is a significant engineering achievement: lattice-based cryptography requires substantially larger key sizes and memory footprints than classical ECC, and fitting it into the resource-constrained Trusted Execution Environment is non-trivial.
The SDK exposes these through the standard KeyPairGenerator API, meaning developers can adopt quantum-safe signatures without proprietary cryptographic implementations.
3. Ecosystem-Scale App Signing
Perhaps the most operationally interesting piece is Play App Signing's hybrid signature approach. Google Play automatically generates "hybrid" signature blocks that combine classical (RSA/ECDSA) and PQC (ML-DSA) keys. This preserves compatibility with older Android versions while adding quantum-resistant protection.
For new apps, ML-DSA signing keys are generated automatically. For existing apps, developers opt in, and Google Cloud KMS handles the signing key management. Google Play also begins prompting developers to rotate signing keys at least every two years — a practice that becomes essential when quantum-vulnerable keys must be replaced within a known, short window.
What Infrastructure Operators Should Do Now
1. Inventory Long-Lived Keys
Every cryptographic key that lives longer than 5 years is at risk. Root CA certificates, code-signing certificates, SSH host keys, VPN gateway certificates, API signing keys — document them all, their validity periods, and their rotation procedures.
2. Enable Post-Quantum Encryption Now
Cloudflare, Google, and other major CDNs already support post-quantum TLS key agreement (X25519Kyber768 or similar). If you use Cloudflare, post-quantum encryption is already active for most traffic. If you manage your own TLS termination, check whether your stack supports hybrid key agreement — nginx with BoringSSL, for instance, can be compiled with PQC support.
3. Plan Certificate Migration
Certificate Authorities are beginning to offer post-quantum certificates. Let's Encrypt, a critical part of the web PKI, will need to migrate its entire issuance pipeline. The timeline is tight: if major CAs do not support PQC certificates by 2028, organisations with 2029-expiring certificates face a gap.
4. Audit Software Supply Chain Signing
Software update mechanisms are among the most dangerous downgrade targets. If your infrastructure uses TUF (The Update Framework), in-toto, or similar frameworks, verify that they support hybrid signatures. GitHub's sigstore and cosign are already experimenting with PQC.
5. Build Crypto-Agility
The specific algorithms that survive the transition to post-quantum cryptography may not be the ones standardised today. ML-KEM (FIPS 203) and ML-DSA (FIPS 204) are the current NIST standards, but the ongoing "On-ramp" standardisation round may produce additional signature schemes. Design systems so that cryptographic primitives are abstracted behind clean interfaces, not hard-coded.
The Cloudflare Timeline
Cloudflare's accelerated roadmap is instructive for any organisation planning its own migration:
- 2022: Post-quantum encryption by default for all websites and APIs (mitigating harvest-now/decrypt-later)
- 2026: Full inventory of authentication infrastructure, begin PQC certificate testing
- 2027-2028: Migrate internal authentication to PQC; support PQC client certificates
- 2029: Full post-quantum security, including authentication — all keys, certificates, and signatures use PQC or hybrid schemes
The critical insight from Cloudflare's analysis is that authentication migration is harder than encryption migration. Encryption can be upgraded server-side with relatively little coordination. Authentication requires every client to support the new scheme simultaneously — a coordination problem across the entire internet.
Conclusion
The post-quantum migration timeline has shortened from a comfortable 10-15 year horizon to something approaching 3-5 years. Google's algorithm breakthrough and Oratomic's neutral-atom estimates are the proximate causes, but the underlying dynamic is that progress on quantum computing is accelerating on all fronts simultaneously.
The industry response — Cloudflare targeting 2029, Google embedding PQC in Android 17, NIST finalising standards — is encouraging, but the coordination problem remains. Internet security infrastructure is a global commons; its weakest links determine its overall strength.
For operators of internet infrastructure, the task is clear: inventory cryptographic assets, enable hybrid schemes where possible, and build the organisational capacity to rotate keys at scale within a known timeframe. The deadline is no longer abstract.