Lattices.io — Mathematical Lattices & Post-Quantum Cryptography

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.

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.

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 Levels 1–5

Level 1: Breaking this costs at least as much as an exhaustive key search for AES-128 — currently $2^{128}$ operations. Recommended minimum for most applications.

Level 3: At least as hard as breaking AES-192. A comfortable margin for sensitive data.

Level 5: At least as hard as breaking AES-256. Maximum security, for long-lived critical infrastructure.

Kyber-512 targets Level 1; Kyber-768 targets Level 3; Kyber-1024 targets Level 5. Most deployments use Kyber-768 as a reasonable balance of security and performance.

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.