Post-Quantum Security — Lattices Against Quantum Computers

Most encryption in use today — the kind protecting your bank account, your messages, your TLS connection to every website — relies on two mathematical problems: integer factorization and the discrete logarithm. RSA depends on factoring. Diffie-Hellman and elliptic curve cryptography depend on discrete log.

Both of these problems will become trivially solvable once a sufficiently powerful quantum computer exists. Not "somewhat faster" — actually trivial. A quantum computer running Shor's algorithm would factor a 2048-bit RSA key in minutes rather than the billions of years it would take a classical computer. This is not a theoretical curiosity: it means everything encrypted with RSA or ECC today becomes readable the moment large quantum computers arrive.

Lattice-based cryptography was developed to survive this transition.

Beginner's Intuition 💡

Imagine modern encryption (like RSA) as a padlock whose combination is made by multiplying two massive prime numbers together. For standard computers, guessing the original numbers is like trying to un-bake a cake—nearly impossible.

But a Quantum Computer works fundamentally differently. It can "look" at all possible combinations simultaneously using quantum physics and pop the lock instantly. Lattice cryptography completely sidesteps this problem. It's like replacing the combination lock with a massive, multi-dimensional maze that is equally confusing for both normal computers and quantum computers.

Shor's Algorithm: What Quantum Computers Break

Peter Shor's 1994 algorithm is remarkable because it exploits a specific mathematical structure — called the abelian hidden subgroup structure — that underlies both factoring and discrete log. Quantum computers can solve the hidden subgroup problem efficiently by exploiting quantum interference. Once you frame factoring and discrete log as hidden subgroup problems, a quantum computer cracks them in polynomial time.

RSA — broken by Shor

RSA's security rests on the difficulty of factoring a large number $N = p \cdot q$ into its prime factors. Classical algorithms need roughly $e^{1.9 (\log N)^{1/3}}$ operations (sub-exponential, but huge). Shor's algorithm factors $$N$$ in time polynomial in $\log N$ — fast enough to break 2048-bit RSA in minutes on a large quantum computer.

Elliptic curves — broken by Shor

ECDSA, ECDH, and all elliptic curve schemes rely on the discrete logarithm over elliptic curve groups. Shor's algorithm applies here too. A 256-bit ECC key — currently considered equivalent to 128 bits of security — provides essentially zero security against a quantum adversary with enough qubits.

Diffie-Hellman — broken by Shor

Classical DH (over integers) and its elliptic curve variant are both vulnerable. This breaks most deployed key exchange protocols: early TLS versions, SSH (without PQC extensions), and Signal Protocol's initial key exchange. The key agreement step is where the attack lands.

What Quantum Computers Don't Break: Symmetric Keys and Hashes

Grover's algorithm (1996) is the other major quantum attack. It provides a quadratic speedup for brute-force search over unstructured data. This affects symmetric cryptography (AES) and hash functions (SHA-256) — but only by halving the effective security level in bits. AES-256 drops from 256 bits of security to 128 bits. That's still fine — you just need to use the 256-bit version instead of the 128-bit version. Symmetric cryptography is largely "post-quantum ready" just by doubling key sizes.

Why Lattices Resist Quantum Attacks

Lattice problems — SVP, CVP, LWE — do not have the hidden subgroup structure that Shor's algorithm exploits. No one has found a way to encode "find the shortest vector" as a hidden subgroup problem. The best quantum algorithms for lattice problems are classical algorithms with quantum speedups in inner loops via Grover's algorithm — giving only a modest 10–20% reduction in security bits, not the exponential collapse seen with factoring and discrete log.

Best known quantum attacks on lattices

Quantum sieving (Laarhoven, 2016): Time $2^{0.2653n}$ versus classical $2^{0.2075n}$ . The exponent is about 28% larger quantum — a mild penalty, not a break.

Quantum enumeration: At most a quadratic (Grover) speedup in the search.

No exponential quantum speedup is known for SVP or LWE. This is why NIST chose lattice-based algorithms as the primary post-quantum standards.

NIST Timeline — From Call to Final Standards

The NIST Post-Quantum Cryptography standardization process is the largest coordinated global cryptographic evaluation in history. It ran for eight years and involved hundreds of researchers from academia, industry, and government worldwide.

NIST PQC Standardization Timeline

December 2016 — Call for proposals. NIST published its requirements and invited the global cryptographic community to submit post-quantum algorithm candidates. 69 complete submissions were received (plus 13 incomplete). Candidates were required to address key encapsulation, public-key encryption, and digital signatures.

January 2019 — Round 2 (26 candidates). After initial analysis, NIST advanced 26 algorithms: 17 public-key encryption/KEM and 9 signature schemes. Several early candidates were broken during this round — notably SIKE (supersingular isogeny), which was broken in 62 minutes on a laptop in 2022 using classical mathematics.

July 2020 — Round 3 (7 finalists + 8 alternates). Seven finalists and eight alternate candidates advanced. The finalists included CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, SPHINCS+, NTRU, SABER, and Classic McEliece.

July 2022 — Initial selections announced. NIST selected CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium, Falcon, and SPHINCS+ for digital signatures. These selections were announced before the final standards were written.

August 2024 — Final FIPS standards published. Four standards were finalized: FIPS 203 (ML-KEM, based on Kyber), FIPS 204 (ML-DSA, based on Dilithium), FIPS 205 (SLH-DSA, based on SPHINCS+), and FIPS 206 (FN-DSA, based on Falcon). These are now official US federal standards and de facto global standards for post-quantum cryptography.

Ongoing — Additional signatures. A fourth round for additional signature schemes (not based on lattices, to diversify the portfolio) continues. Candidates include hash-based, code-based, and multivariate schemes.

The NIST Standardization

Starting in 2016, NIST ran a worldwide competition to select post-quantum cryptographic standards. Over 80 candidates were submitted. After multiple rounds of cryptanalysis by the global research community, four algorithms were selected in 2022–2024 and finalized as FIPS standards in August 2024.

FIPS 203 — ML-KEM

Based on Module-LWE (Kyber). The primary standard for key encapsulation — replacing Diffie-Hellman for key exchange in TLS, SSH, and similar protocols. Three security levels: ML-KEM-512 (128-bit), ML-KEM-768 (192-bit), ML-KEM-1024 (256-bit).

FIPS 204 — ML-DSA

Based on Module-LWE and Module-SIS (Dilithium). The primary standard for digital signatures — replacing RSA and ECDSA for code signing, certificates, and authentication. Fast signing and verification; larger signatures than RSA but comparable to ECC.

FIPS 206 — FN-DSA

Based on NTRU lattices (Falcon). A secondary signature standard optimized for small signature sizes(~700 bytes vs Dilithium's ~2.4 KB). More complex to implement securely — requires careful floating-point Gaussian sampling. Used where bandwidth is precious.

FIPS 205 — SLH-DSA

Based on hash functions, not lattices (SPHINCS+). Included as a conservative backupin case lattice assumptions turn out to be wrong. Much larger signatures (8–50 KB). Its security depends only on the collision resistance of hash functions — an assumption most cryptographers are extremely confident in.

Harvest Now, Decrypt Later: Why This Is Urgent Today

A powerful quantum computer capable of running Shor's algorithm doesn't exist yet. The current record is a few hundred noisy qubits; breaking 2048-bit RSA would require millions of error-corrected logical qubits. Estimates for when this becomes feasible range from 10 to 30 years.

So why act now? Because of a strategy called "harvest now, decrypt later": a sophisticated adversary intercepts and stores encrypted network traffic today, waits until they have a quantum computer, then decrypts everything retroactively. If you're protecting data whose secrecy matters in 2035, you need to encrypt it with post-quantum algorithms today — even if large quantum computers are still years away.

This is why governments, major tech companies, and standards bodies are moving rapidly. Google, Cloudflare, and AWS have already deployed ML-KEM in production. Apple added post-quantum protections to iMessage in 2024. The migration is already underway.

Security Levels

NIST defines five security levels as a common reference point. Each level corresponds to the computational cost required to break the scheme — measured against the best known classical and quantum attacks.

NIST Security Level Definitions

NIST defines security levels by reference to the cost of attacking well-understood symmetric primitives, not by an abstract bit count. This ties PQC security directly to a benchmark the community already trusts.

Level 1 (~128 bits classical, ~128 bits quantum): At least as hard as an exhaustive key search for AES-128 — requiring approximately $2^{128}$ operations with the best known classical attacks, and at least $2^{64}$ quantum operations (Grover's algorithm gives a quadratic speedup on key search). This is the minimum recommended for new deployments.

Level 2 (between 1 and 3): At least as hard as finding a collision in SHA-256 — approximately $2^{128}$ operations via birthday attack.

Level 3 (~192 bits classical, ~192 bits quantum): At least as hard as breaking AES-192. Recommended for data requiring long-term protection (beyond 2040) or where extra margin against algorithmic improvements is desired.

Level 4 (between 3 and 5): At least as hard as finding a collision in SHA-384.

Level 5 (~256 bits classical, ~256 bits quantum): At least as hard as breaking AES-256. Maximum security, for critical infrastructure, long-lived root certificates, and applications where security must remain unbroken beyond 2050.

Concrete instantiations:
ML-KEM-512 / ML-DSA-44 / Falcon-512: Level 1
ML-KEM-768 / ML-DSA-65: Level 3 (most recommended for general use)
ML-KEM-1024 / ML-DSA-87 / Falcon-1024: Level 5

Note: "quantum security" for lattice schemes does not simply halve the classical security. Quantum sieving improves the exponent by ~28%, not a factor of 2. A Level 1 lattice scheme provides ~128 bits against quantum attackers (not ~64 bits as for AES-128 under Grover).

How Security Estimates Work

Picking LWE parameters is not guesswork — it follows a rigorous methodology. The standard approach, called the Core-SVP model, estimates the cost of the best known lattice attack on the specific LWE instance underlying the scheme. The tool used by all NIST candidates is the Lattice Estimator (Albrecht et al.), which considers all known classical and quantum algorithms and outputs a security estimate in bits.

The result: Kyber-768 provides approximately 180 bits of classical security and 165 bits of quantum security, well above the 128-bit target. The gap provides a safety margin against unforeseen algorithmic improvements — a lesson learned from the history of RSA, where key sizes needed to increase repeatedly as factoring algorithms improved.

Migration Strategy — Hybrid Classical + PQC During the Transition

Migrating from classical to post-quantum cryptography is not a switch that flips overnight. The transition period — where both classical and quantum computers coexist — requires careful strategy to maintain security against both classical and quantum adversaries simultaneously.

Hybrid Key Exchange

A hybrid key exchange combines a classical key agreement (e.g., X25519 elliptic curve Diffie-Hellman) with a post-quantum key encapsulation (e.g., ML-KEM-768) in a single protocol. The shared secret is the hash of both outputs:

$K = H(K_{\text{classical}} \| K_{\text{PQC}})$

Security guarantee: the combined key is secure as long as either the classical or the post-quantum component is secure. Against a classical-only adversary today, X25519 provides the security. Against a future quantum adversary, ML-KEM provides the security. No single failure breaks both simultaneously.

Deployed examples: Google Chrome deployed X25519+Kyber768 in 2023. AWS, Cloudflare, and Apple iMessage have all deployed hybrid schemes. RFC 9370 standardizes hybrid key exchange for TLS 1.3.

Migration Phases and Priorities

Phase 1 — Inventory (now): Identify all cryptographic assets: what algorithms are used, where, by whom, and what data they protect. Understand the data lifetime: data that must remain confidential past 2035 needs PQC protection today (harvest now, decrypt later).

Phase 2 — Deploy hybrid (2024–2027): Replace key exchange with hybrid X25519 + ML-KEM in all internet-facing protocols (TLS, SSH, VPN). This protects against harvest-now-decrypt-later without requiring full trust in PQC algorithms yet. Hybrid signatures are also possible but less common since signature data is not stored long-term.

Phase 3 — Full PQC migration (2027–2030): Replace classical algorithms entirely in all new systems. Deploy ML-DSA or FN-DSA for code signing, certificates, and authentication. Update PKI infrastructure (root CAs, intermediate CAs, certificate chains) to use PQC keys.

Phase 4 — Sunset classical algorithms (2030+): NIST plans to deprecate RSA and ECC for most uses by 2030 and disallow them by 2035. NSA CNSA 2.0 (Commercial National Security Algorithm Suite) requires PQC for all new national security systems starting 2025 and mandates full migration by 2033.

Key challenges: Hardware security modules (HSMs), smart cards, and embedded devices often cannot be remotely updated. Long-lived certificates (root CAs typically have 20–25 year validity) must be replaced. Legacy industrial control systems may have 30+ year lifetimes and require physical replacement rather than software updates.

Why not wait?

Harvest-now-decrypt-later makes waiting dangerous. Encrypted network traffic captured today can be stored and decrypted when quantum computers arrive. For long-lived secrets — diplomatic communications, medical records, financial data — the threat exists today even though large quantum computers don't yet.

Why not switch immediately?

Post-quantum algorithms are newer and have received less cryptanalysis than RSA or ECC. Hybrid schemes provide a hedge: if a PQC algorithm is broken tomorrow, the classical component still protects data encrypted today. Hybrid is the right engineering choice during the transition.

Crypto agility

Build systems to be crypto-agile: abstract the algorithm from the protocol, so algorithms can be swapped without redesigning the protocol. TLS 1.3's cipher suite negotiation is an example — adding a new KEM is a configuration change, not a protocol redesign. This lesson, if learned before PQC, makes future transitions much cheaper.