RSA, the algorithm that secures virtually every HTTPS connection, digital signature, and certificate authority chain on the internet, will be broken by a sufficiently large quantum computer running Shor’s algorithm. Not weakened. Not degraded. Broken completely – reduced from computationally infeasible to solvable in polynomial time. The same fate awaits elliptic curve cryptography (ECC), Diffie-Hellman key exchange, DSA, and every asymmetric cryptographic scheme built on the hardness of integer factorization or the discrete logarithm problem.
This is not speculation. The mathematics of Shor’s algorithm has been verified repeatedly since Peter Shor published it in 1994. The only uncertainty is when – not whether – quantum hardware will reach the scale required to execute it against production key sizes. NIST estimates this timeline at 10-20 years. The National Academy of Sciences puts it at 10-30 years. China’s quantum computing program has publicly stated a goal of cracking RSA-2048 by 2035.
The response is already in production. In August 2024, NIST published three post-quantum cryptographic standards: ML-KEM (based on CRYSTALS-Kyber), ML-DSA (based on CRYSTALS-Dilithium), and SLH-DSA (based on SPHINCS+). Signal, Apple, Google Chrome, and Cloudflare have already deployed post-quantum key exchange in production systems. The migration has started. The question is whether it will finish before the threat materializes.
What Shor’s Algorithm Breaks
Shor’s algorithm provides an efficient quantum procedure for two problems:
Integer factorization. Given N = p * q (where p and q are large primes), find p and q. RSA’s security relies on this being hard. Shor’s algorithm solves it in O((log N)^3) time on a quantum computer – exponentially faster than the best classical algorithm (General Number Field Sieve, which runs in sub-exponential time).
Discrete logarithm. Given g^x mod p, find x. Diffie-Hellman key exchange, DSA, and ECDSA all rely on variants of this problem. Shor’s algorithm solves all of them.
The Scope of Destruction
Every system that depends on these hardness assumptions is vulnerable:
- TLS/HTTPS: The handshake uses RSA or ECDHE for key exchange. Break the key exchange, and all session traffic is decryptable.
- Digital signatures: Code signing, certificate authorities, DNSSEC, S/MIME, PGP – all use RSA or ECC signatures.
- Cryptocurrency: Bitcoin uses ECDSA (secp256k1). Ethereum uses ECDSA. Every blockchain signature scheme based on elliptic curves is vulnerable.
- SSH: Key exchange and authentication use RSA, ECDSA, or Ed25519 (all vulnerable).
- E2EE messaging: The Signal Protocol uses Curve25519 for X3DH and the DH ratchet. Without post-quantum upgrades, a quantum computer could break every key exchange.
What Shor’s Algorithm Does NOT Break
Symmetric cryptography survives. AES-256 is not based on factorization or discrete logarithms. Grover’s algorithm provides a quadratic speedup for brute-force search, reducing AES-256’s effective security from 256 bits to 128 bits. A 128-bit security level remains well beyond any feasible attack. AES-256-GCM, the encryption standard behind Stealth Cloud, is post-quantum survivable.
Hash functions survive. SHA-256, SHA-3, BLAKE3 – all maintain at least 128-bit security against quantum attacks (Grover reduces the collision resistance of an n-bit hash from 2^(n/2) to 2^(n/3), which for SHA-256 is still 2^85 – far beyond practical).
Lattice-based cryptography survives. The mathematical problems underlying the NIST post-quantum standards – Learning With Errors (LWE), Module-LWE, and Short Integer Solution (SIS) – have no known efficient quantum algorithms. This is why lattice-based schemes were selected.
The NIST Post-Quantum Standards
NIST’s post-quantum standardization process began in 2016, received 82 submissions, and completed its primary selections in August 2024 after three rounds of evaluation. The process was arguably the most rigorous public cryptographic standardization effort in history, involving hundreds of researchers over eight years.
ML-KEM (CRYSTALS-Kyber): Key Encapsulation
ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism), based on CRYSTALS-Kyber, replaces RSA and ECDH for key exchange. It is a key encapsulation mechanism (KEM) – a protocol for establishing a shared secret between two parties.
How it works: ML-KEM is built on the Module Learning With Errors (MLWE) problem. Alice generates a public/private key pair based on a random matrix A and a secret vector s with small coefficients. To encapsulate a key, Bob generates a random message, encrypts it using Alice’s public key (adding noise from the LWE problem), and sends the ciphertext. Alice decrypts using her secret key, recovering the shared secret.
Parameter sets:
| Parameter Set | Security Level | Public Key Size | Ciphertext Size | Shared Secret |
|---|---|---|---|---|
| ML-KEM-512 | ~AES-128 | 800 bytes | 768 bytes | 32 bytes |
| ML-KEM-768 | ~AES-192 | 1,184 bytes | 1,088 bytes | 32 bytes |
| ML-KEM-1024 | ~AES-256 | 1,568 bytes | 1,568 bytes | 32 bytes |
Compared to X25519 (32-byte public keys, 32-byte shared secrets), ML-KEM keys are 25-50x larger. This is a meaningful but manageable cost for TLS handshakes.
Performance: ML-KEM key generation and encapsulation are faster than RSA at equivalent security levels. On modern x86 hardware, ML-KEM-768 key generation takes approximately 30 microseconds, encapsulation takes 40 microseconds, and decapsulation takes 40 microseconds. These are faster than RSA-2048 (which takes 1-2 milliseconds for key generation).
ML-DSA (CRYSTALS-Dilithium): Digital Signatures
ML-DSA replaces RSA and ECDSA for digital signatures. It is also lattice-based (Module-LWE/SIS), providing consistency with ML-KEM.
Parameter sets:
| Parameter Set | Security Level | Public Key Size | Signature Size |
|---|---|---|---|
| ML-DSA-44 | ~AES-128 | 1,312 bytes | 2,420 bytes |
| ML-DSA-65 | ~AES-192 | 1,952 bytes | 3,293 bytes |
| ML-DSA-87 | ~AES-256 | 2,592 bytes | 4,595 bytes |
Compared to ECDSA (64-byte signatures, 33-byte public keys), ML-DSA signatures are 40-70x larger. For bandwidth-constrained environments (IoT, blockchain), this size increase is the primary deployment challenge.
SLH-DSA (SPHINCS+): Hash-Based Signatures
SLH-DSA provides a backup digital signature standard based entirely on hash functions, with no lattice assumptions. Its security rests solely on the collision resistance of the underlying hash function – an assumption that has been studied for decades and is among the most conservative in cryptography.
The trade-off: SLH-DSA signatures are large (7-49 KB depending on parameter set) and signing is slow (10-100x slower than ML-DSA). But if lattice-based schemes are ever found to be vulnerable (a theoretical possibility, however unlikely), SLH-DSA provides a fallback that does not share the same mathematical assumptions.
The Harvest Now, Decrypt Later Threat
The most immediate and concrete quantum threat is not future key exchange – it is past traffic. Intelligence agencies and state-sponsored actors are widely believed to be recording encrypted network traffic today, storing it until quantum computers can decrypt it.
This attack model is called harvest now, decrypt later (HNDL). Its implications are severe:
- Diplomatic communications encrypted with RSA or ECDHE today can be decrypted in 10-20 years.
- Corporate trade secrets, M&A negotiations, and strategic communications captured today have long-term value.
- Medical records, genetic data, and personal communications may remain sensitive for the lifetime of the individuals involved.
- Intelligence agencies have the storage capacity (the NSA’s Utah Data Center has an estimated 3-12 exabytes of storage) and the institutional patience to execute this strategy.
For data with a sensitivity lifetime shorter than the quantum timeline (a restaurant reservation, a meme, a shopping list), HNDL is irrelevant. For data with decades-long sensitivity, the threat is active today – before a single cryptographically relevant quantum computer exists.
This is why Signal implemented PQXDH (post-quantum X3DH) in September 2023 and Apple shipped PQ3 for iMessage in February 2024. Both use hybrid approaches: the classical key exchange (X25519) is combined with a post-quantum KEM (Kyber/ML-KEM), and the shared secret is derived from both. An attacker must break both the classical and post-quantum components to recover the key.
The Quantum Timeline: How Close Are We?
The critical metric is the number of logical qubits – error-corrected, stable qubits capable of sustained computation. Breaking RSA-2048 with Shor’s algorithm requires approximately 4,000 logical qubits. Breaking elliptic curve cryptography (256-bit) requires approximately 2,500 logical qubits.
Current state of the art (early 2026):
- IBM: Condor processor (1,121 physical qubits, 2023). Heron processor (133 physical qubits, higher fidelity). Roadmap targets 100,000+ physical qubits by 2033.
- Google: Willow processor (105 physical qubits, 2024) demonstrated quantum error correction below the threshold – a critical milestone. Google’s roadmap targets a “useful” quantum computer by 2030.
- Quantinuum: H2 processor (56 trapped-ion qubits, 2024) with industry-leading gate fidelity (99.8% two-qubit gates). Targeting 100+ logical qubits by 2028.
The conversion ratio between physical and logical qubits depends on error rates. With current error rates, approximately 1,000-10,000 physical qubits are needed per logical qubit. Google’s Willow result improved this ratio significantly, but breaking RSA-2048 still requires on the order of 4-20 million physical qubits.
Conservative estimates (RAND Corporation, 2023): A cryptographically relevant quantum computer is 15-30 years away. Moderate estimates (Global Risk Institute, 2024): 50% probability by 2038-2042. Aggressive estimates (some Chinese research teams): Potentially achievable by 2035 with breakthroughs in error correction.
The variance in these estimates reflects genuine scientific uncertainty. The question for security architects is not “when exactly?” but “can my migration complete before the fastest plausible timeline?”
Migration Strategy: What Organizations Should Do Now
NIST’s migration guidance (SP 800-227, draft 2025) recommends a phased approach:
Phase 1: Inventory (Now)
Identify every cryptographic dependency in your infrastructure – TLS certificates, SSH keys, VPN configurations, code signing certificates, API authentication, database encryption, backup encryption. Map which algorithms are used where.
Phase 2: Hybrid Deployment (2025-2027)
Deploy hybrid key exchange (classical + post-quantum) for all new connections. This is already supported in:
- TLS 1.3: Chrome, Firefox, and Cloudflare support X25519Kyber768 hybrid key exchange.
- SSH: OpenSSH 9.0+ supports hybrid key exchange using NTRU + X25519.
- Signal/iMessage: Already deployed in production.
Hybrid mode ensures no security regression: if the PQ algorithm is later found to be flawed, the classical algorithm still protects against classical attacks.
Phase 3: Full Migration (2027-2030)
Replace all remaining classical-only asymmetric cryptography with post-quantum or hybrid alternatives. This includes:
- Certificate authority chains (requires ecosystem-wide coordination)
- Code signing infrastructure
- Long-term archive encryption (re-encrypt with PQ algorithms)
- Blockchain systems (the most challenging migration due to decentralized governance)
Phase 4: Deprecation (2030+)
Remove classical-only asymmetric cryptography from production systems. Mandate PQ-only or hybrid for all connections.
The Cost of Migration
The economic burden of post-quantum migration is unevenly distributed. Large technology companies with dedicated cryptography teams – Google, Apple, Cloudflare, Amazon – have already shipped hybrid PQ implementations. For them, the cost is engineering time, measured in person-years, absorbed within existing security budgets.
For the broader ecosystem, the costs are more significant:
Certificate infrastructure. The global PKI ecosystem – certificate authorities, root stores, certificate transparency logs – must transition to PQ signatures. This affects every website, every code signing certificate, and every email encryption system. The CA/Browser Forum is evaluating PQ certificate profiles, but the timeline for mandatory adoption remains undefined as of early 2026.
Embedded and IoT devices. Devices with constrained processors and limited firmware update capabilities – industrial controllers, medical devices, automotive ECUs – may not support PQ algorithms. The larger key and signature sizes of ML-KEM and ML-DSA require more memory, more bandwidth, and more processing power than classical alternatives. Devices with 10-15 year operational lifetimes deployed today may remain vulnerable for their entire service life.
Bandwidth impact. The increased size of PQ keys and signatures adds measurable overhead to TLS handshakes. An ML-KEM-768 key exchange adds approximately 2 KB to the handshake compared to X25519. For a single connection, this is negligible. For a CDN serving billions of connections per day, the aggregate bandwidth cost is meaningful. Cloudflare’s measurements from their early PQ deployment showed a 5-10% increase in handshake latency on slow networks.
Compliance cost. Organizations subject to CMMC (Cybersecurity Maturity Model Certification), FedRAMP, or similar frameworks will need to demonstrate PQ readiness. NIST’s draft transition timeline (SP 800-227) suggests that federal agencies should deprecate classical-only algorithms by 2030 and mandate PQ by 2035. The compliance audit burden for this transition will be substantial.
Impact on Zero-Knowledge Systems
Zero-knowledge proof systems face a bifurcated quantum future:
zk-SNARKs (elliptic curve based): Vulnerable. Groth16, the most widely deployed SNARK scheme, relies on elliptic curve pairings that Shor’s algorithm breaks. Every zk-SNARK-based blockchain system (Zcash, many ZK rollups) will need to migrate.
zk-STARKs (hash based): Resistant. STARKs rely on hash function collision resistance, which survives quantum attacks. This is one of STARKs’ primary advantages over SNARKs and a key reason StarkNet chose STARKs as its proof system.
Lattice-based ZKPs: An active research area. Schemes based on Module-SIS/LWE can provide both post-quantum security and zero-knowledge properties, but performance is not yet competitive with SNARKs or STARKs for production use.
The Stealth Cloud Perspective
Post-quantum cryptography is not a future concern – it is a present-tense infrastructure requirement for any system handling data with long-term sensitivity. The harvest-now-decrypt-later threat means that every unprotected key exchange happening today is a potential future compromise. Stealth Cloud’s architecture uses AES-256-GCM for symmetric encryption (quantum-survivable) and is designed for hybrid post-quantum key exchange at the transport layer, ensuring that ephemeral sessions are protected against both classical and quantum adversaries from day one.