post quantum crypto intermediate · 22 min read · April 22, 2026

Post-Quantum Cryptography: The Threat Model

Shor's algorithm doesn't break all cryptography — it breaks the specific subset built on integer factoring and discrete logarithms, which happens to be nearly every public-key system in production. This tutorial lays out the precise threat model, the 'harvest now, decrypt later' attack, NIST's standardization response, and exactly which of your primitives to replace first.

Prerequisites: Tutorial 12: Shor's Algorithm

This is where quantum knowledge converts to actual short-term revenue. RSA-2048 won’t be broken by a quantum computer this year or next, but enterprises are migrating off it now — because encrypted traffic captured today can be decrypted tomorrow when a Shor-capable quantum computer arrives. NIST finalized its first post-quantum cryptography standards in August 2024. Every bank, government, healthcare system, and SaaS with compliance obligations is either in the middle of a migration or about to start one.

This tutorial lays out the threat model carefully: what Shor actually breaks, what Grover does, what NIST standardized, and the concrete timeline that turns this from hype into a real consulting engagement.

What Shor actually breaks

Recap from Tutorial 12: Shor’s algorithm solves the integer factorization problem — given a composite $N$, find a nontrivial factor — in polynomial time on a quantum computer. A simple variant solves the discrete logarithm problem: given $g^x \bmod p$, find $x$.

Every public-key cryptosystem whose security relies on either of these problems being hard is broken:

Factoring-based:

• RSA encryption and signatures (all key sizes)
• Rabin cryptosystem

Discrete-log-based:

• Diffie-Hellman key exchange
• DSA signatures
• ElGamal encryption
• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve DSA (ECDSA)
• Edwards-curve Digital Signature Algorithm (Ed25519, Ed448)

That’s essentially every public-key primitive in production today. The only widely-deployed public-key systems Shor doesn’t break are those based on completely different mathematical problems — lattice-based, code-based, hash-based, isogeny-based. Those are the post-quantum candidates.

What Grover does (and doesn’t)

Grover’s algorithm gives a quadratic speedup on unstructured search. Applied to a symmetric cipher of $k$-bit key:

• Classical brute force: $2^{k-1}$ expected operations
• Quantum brute force: $2^{(k-1)/2}$ operations

Effect: halve the effective bit security. AES-256 provides 128-bit post-quantum security, AES-128 provides only 64-bit (dangerous). SHA-256 preimage resistance drops from 256 to 128 bits (fine for now, but tight).

This is a much milder effect than Shor. The post-quantum response for symmetric crypto is simply to double key lengths. You don’t need to replace the algorithms.

Symmetric primitive	Pre-quantum security	Post-quantum security (Grover)	Post-quantum recommendation
AES-128	128 bits	64 bits	Retire — move to AES-256
AES-256	256 bits	128 bits	Safe
SHA-256	256 bits preimage	128 bits	Safe (tight)
SHA-384, SHA-512	384-512 bits	192-256 bits	Safe
HMAC-SHA-256	256 bits	128 bits	Safe

Harvest now, decrypt later

Here’s why the migration is urgent despite the timeline:

Any encrypted traffic you send today can be captured by a patient adversary (a state actor, a large criminal group, anyone with enough storage) and decrypted later when a sufficiently large quantum computer exists. If your data is valuable for more than the quantum-computer arrival time, it’s already at risk.

Concretely:

• TLS handshake from 2026 protecting banking transactions: if the session key was exchanged via RSA-2048 or ECDH, and the underlying data is valuable in 2035, that data is at risk.
• Long-lived government classified data (diplomatic cables, intelligence reports): traffic encrypted today with ECDH will be readable by the 2030s.
• Genetic databases, healthcare records: valuable for decades; currently encrypted at-rest with RSA-wrapped AES keys. The RSA wrapping is the weak link.
• IoT root keys and firmware signing keys: long device lifetimes. A device deployed today may receive authenticated firmware updates for 10+ years.

The critical question is not “when will Shor break RSA” but “how long does the data need to stay secret?” If the answer is ≥ 10 years, your current crypto is insufficient.

NIST’s PQC standardization

NIST ran a public competition from 2016 to 2024, evaluating dozens of candidate post-quantum algorithms. August 2024 finalized three standards:

• FIPS 203 / ML-KEM (Module-Lattice-based Key Encapsulation Mechanism, formerly CRYSTALS-Kyber). The PQC replacement for RSA-OAEP and ECDH.
• FIPS 204 / ML-DSA (Module-Lattice-based Digital Signature Algorithm, formerly CRYSTALS-Dilithium). The PQC replacement for RSA-PSS and ECDSA.
• FIPS 205 / SLH-DSA (Stateless Hash-Based Digital Signature Algorithm, formerly SPHINCS+). Backup signature scheme based on hashes only — hedges against lattice attacks.

Additional candidates still in evaluation:

• Falcon (lattice-based signatures, specialized niche applications)
• Classic McEliece (code-based KEM, very large public keys, niche use)
• BIKE, HQC (code-based KEMs, expected in 2026-2027 NIST Round 4)

What to use in production today (2026):

• ML-KEM-768 for key encapsulation (replaces RSA-2048 / ECDH with NIST Category 3 security)
• ML-DSA-65 for signatures (replaces RSA-2048 / ECDSA with NIST Category 3 security)
• Hybrid mode for both — use ML-KEM + ECDH simultaneously during the migration period (defense in depth)

Lattice-based cryptography in one paragraph

Why do we believe lattices are quantum-safe? The hardness assumption: finding short vectors in a random high-dimensional integer lattice (Learning With Errors, LWE; or its structured variant Module-LWE). No known quantum algorithm beats classical best-known algorithms significantly on these problems. Shor’s algorithm relies on exploiting periodic group structure; lattice problems lack the kind of exploitable structure Shor needs.

Caveat: this is a belief, not a proof. If someone publishes “Shor-like algorithm for LWE” tomorrow, ML-KEM falls. That’s why NIST also standardized SLH-DSA (hash-based) as a backup — completely different mathematical foundation.

The migration phases

A typical enterprise PQC migration follows four phases:

Phase 1: Inventory (months 1-3)

You cannot migrate what you haven’t found. Catalog every place cryptography is used:

• TLS endpoints (internal and external)
• VPN tunnels and IPsec
• SSH keys (developer workstations, server authentication)
• Code-signing certificates (App Store, Google Play, Authenticode)
• Certificate chains and PKI
• Document signing (PDF signatures, S/MIME)
• Hardware security modules (HSMs)
• Database encryption-at-rest keys
• Cryptographic primitives in application code

For most companies, this is a year-long project by itself. This is where consulting engagements live.

Phase 2: Risk Prioritization (months 2-6)

Not all crypto needs to be migrated at the same pace. Sort by:

• Data longevity. Data valuable for under 5 years: migrate by 2030. For 10+ years: migrate now.
• Network exposure. Internet-facing traffic has highest harvest-now-decrypt-later risk.
• Replacement difficulty. Code-signing keys have long rotation cycles; migrate first.
• Regulatory requirements. Compliance frameworks (FedRAMP, FIPS, ISO 27001) are adding PQC requirements; targeting those specifically accelerates timelines.

Phase 3: Deploy Hybrid (months 6-18)

Hybrid mode means using classical and PQC algorithms together — the session key is the XOR (or KDF combination) of a classical-derived key and a PQC-derived key. Break either and you’re safe; break both and the protocol fails (which is already post-quantum compromised anyway).

Example: hybrid TLS 1.3. The client and server negotiate both an X25519 key and an ML-KEM-768 key; the session key combines both. IETF draft draft-ietf-tls-hybrid-design specifies the mechanics. Deployed by Cloudflare, Google Chrome (as of 2023), AWS, Microsoft. This is the production-grade “safe during migration” setup.

Phase 4: Pure PQC (2030-2035)

Once all endpoints support PQC and the classical crypto is deprecated. This is where compliance frameworks mandate ML-KEM-only endpoints. Most enterprises won’t get here before 2030.

Timeline realities

How long until “Shor breaks RSA-2048”?

Per Gidney-Ekerå 2021: ~20M physical qubits, ~8 hours. Current hardware (Willow, Nighthawk, Quantinuum H2): thousands of physical qubits. Scale gap: 4 orders of magnitude. Historical scaling rate: physical qubit count ~doubles every 18-24 months (IBM’s roadmap). At that rate, 20M qubits is ~2033-2036.

Reality check numbers from the community:

• Global Risk Institute survey 2024: 27% of experts think RSA-2048 falls before 2034; 50% before 2039.
• IBM Starling roadmap: 200 logical qubits by 2029, path to thousands of logical qubits by 2033.
• NIST guidance: “migrate by 2035” is the canonical planning horizon. “Complete deprecation of RSA-2048 by 2030” is the aggressive posture.

For any data that needs to stay secret past 2035, migrate now. For transactional data that needs ~2-year secrecy, you have until ~2032 to migrate. But you don’t want to be doing a panic migration in 2031 — plan the work now.

What to tell a client

The elevator pitch for PQC consulting / tooling:

The cryptography that protects most of your internet traffic, authentication, and code signing will be broken by a quantum computer, probably sometime in the early-to-mid 2030s. But adversaries can record encrypted traffic today and decrypt it later — which means the window for “harvest now, decrypt later” attacks is already open. NIST has standardized replacement algorithms (August 2024) and the major TLS libraries already support them. A typical enterprise migration project takes 18-36 months. Starting now is the conservative choice; waiting until 2028 is the “we think we’re ok” choice; waiting until 2030+ is the panic-mode choice.

If they ask “why should I pay you specifically” — you’re the person who can read both the quantum threat research and the crypto library implementation details. You’re rare.

Pricing signals

Consulting rates for PQC work as of 2026:

• Inventory audits (Phase 1): $30k-$150k for a mid-sized enterprise, 4-8 weeks of work.
• Migration planning (Phase 2): $50k-$300k, 2-3 months.
• Hybrid TLS deployment (Phase 3): $100k-$1M, 6-18 months depending on scope.
• Ongoing PQC readiness retainer: $5k-$20k/month.

The Big 4 consulting firms (Deloitte, PwC, Accenture, EY) quote 2-5× these numbers with bigger teams and less technical depth. An indie with quantum + crypto depth competes on price and speed.

Exercises

1. Inventory a familiar codebase

Pick an open-source web service codebase. Grep it for cryptographic primitives and categorize: (a) which are quantum-safe today, (b) which are vulnerable to Shor, (c) which are vulnerable to Grover.

Show hint

Grep for: RSA, ECDSA, ECDH, Ed25519, DH, DSA (vulnerable to Shor); AES-128, SHA-1 (problematic even classically); AES-256, SHA-256, ChaCha20 (safe).

2. Data longevity analysis

For a hypothetical healthcare app storing encrypted patient records, compute the data longevity from a privacy-law perspective. What’s the migration deadline?

Show answer

HIPAA/GDPR/equivalent privacy regs typically mandate patient data protection for 7-50 years depending on jurisdiction. Take 20 years as a midpoint. Data encrypted today must be secure until 2046. RSA-2048 is unlikely to survive until 2046 — so encryption-at-rest using RSA-wrapped AES keys needs migration now. The database-encryption keys themselves (if AES-256) are fine; the key-wrapping is the weak link.

3. Estimate Grover impact on bitcoin

What happens to Bitcoin’s proof-of-work (SHA-256-based) under a quantum attacker using Grover?

Show answer

Bitcoin mining is a preimage-finding problem on SHA-256. Grover gives a quadratic speedup — you find a valid block in $\sim 2^{128}$ operations instead of $\sim 2^{256}$. Still impractical today, but the 2× speedup per bit in brute-force difficulty is real. More urgently: Bitcoin signatures are ECDSA, which Shor breaks outright. When/if large quantum computers exist, the signature scheme falls even if mining stays difficult. Bitcoin has discussion threads about migrating to hash-based signatures (Winternitz, LMS) but no implementation yet in 2026.

4. Build a risk score

Propose a weighted risk score formula for crypto primitives in a codebase. Factors: (a) primitive vulnerability (Shor-breaks, Grover-weakens, safe), (b) data longevity (years), (c) network exposure (internal/external), (d) rotation difficulty.

Show a reasonable model

$\text{Risk} = \text{vuln\_weight} \cdot \text{longevity\_years} \cdot \text{exposure} \cdot \text{rotation\_cost}$.

Weights: Shor-vulnerable = 100; Grover-weakens (AES-128) = 10; safe = 1. Exposure: internet-facing = 3, internal = 1. Rotation cost: 1 (easy to rotate) to 10 (hardware-embedded). Higher score = earlier migration priority. A code-signing key for a 10-year-life device, Shor-vulnerable, internet-facing, hard-to-rotate: $100 \cdot 10 \cdot 3 \cdot 10 = 30{,}000$. A TLS ephemeral key for a 1-day session: $100 \cdot 1 \cdot 3 \cdot 1 = 300$. Rank by score, migrate top-to-bottom.

What you should take away

• Shor breaks RSA, ECDSA, ECDH, DH, DSA, and Ed25519. Grover weakens AES-128 but leaves AES-256 and SHA-256+ fine.
• NIST standardized ML-KEM, ML-DSA, and SLH-DSA in August 2024. These are the replacements.
• “Harvest now, decrypt later” is why migration is urgent even though quantum breakthrough is 5-10+ years out.
• The 4-phase migration (inventory → prioritize → hybrid deploy → pure PQC) is a 2-5 year project for a typical enterprise. Phase 1 alone is consulting-revenue territory.
• This is where quantum-education knowledge converts to money. You don’t need to wait for fault-tolerant machines to sell PQC-migration services.

Next: ML-KEM and ML-DSA in Practice — how the standardized algorithms actually work, runnable code, and how they integrate into real TLS and signing infrastructure.

---

Weekly dispatch

Quantum, for people who already code.

One serious tutorial per week, plus the industry moves that actually matter. No hype, no hand-waving.

Email Subscribe

Free. Unsubscribe anytime. We will never sell your email.