Day 4: Lattice Problems — LWE and MLWE

Phase 3 · July 11, 2026

Agenda (2–3 hours)

• Read (75 min): NIST FIPS 203 §3 (notation and background math, pp. 7–15); "A Decade of Lattice Cryptography" — Peikert (2016), §1–3 (free PDF, skim for intuition)
• Study (60 min): LWE and MLWE — why they resist both classical and quantum attacks
• Challenge (30 min): Explain it in plain language

This is the most mathematically dense day of Phase 3.
You won't implement it — you need enough depth to reason about security claims.

Why New Hard Problems?

RSA and ECDH rely on problems in number theory — factoring and discrete logarithm.
These problems have special algebraic structure that Shor's algorithm exploits.

Post-quantum algorithms rely on problems in geometry and algebra that:

1. Have no known polynomial-time quantum algorithm
2. Are well-studied for over 30 years
3. Have provable worst-case to average-case hardness reductions

Learning With Errors (LWE) is the most influential lattice problem.

Learning With Errors (LWE)

Setup: you have a secret vector s ∈ Z_q^n.

The LWE problem: given many pairs (aᵢ, bᵢ) where:

bᵢ = aᵢ · s  +  eᵢ  (mod q)
      ↑           ↑
  public       small random "error"

Can you find s?

Without the error: this is just solving a linear system — trivial with Gaussian elimination.
With small random errors: no known efficient algorithm (classical OR quantum).

The error terms make the system overdetermined and noisy — this kills all known
algebraic and geometric attacks, including those based on quantum Fourier transforms.

Module LWE (MLWE): The Structured Version

LWE is secure but has large key sizes (the matrix A is huge).

Module LWE adds polynomial ring structure:

bᵢ = aᵢ · s  +  eᵢ  (mod q, mod Xⁿ+1)

Operations happen in the polynomial ring Z_q[X]/(X^n + 1).

This structure allows:

• Smaller keys (factor of ~n improvement)
• Faster operations (NTT — Number Theoretic Transform, like FFT for polynomials)
• Same provable security (reduces to LWE under standard assumptions)

ML-KEM and ML-DSA are both built on MLWE and its related problem MSIS.

Why Quantum Doesn't Help

Shor's works because discrete log and factoring have hidden periodic structure
that the Quantum Fourier Transform can detect.

LWE/MLWE have no such periodic structure. The error terms destroy it.

The best known quantum algorithm for LWE (BKZ with quantum subroutines) gives
only a modest speedup — not polynomial time. NIST sizes ML-KEM parameters to
have 128+ bits of post-quantum security even accounting for this speedup.

This is unlike RSA/ECDH where the quantum speedup is from exponential → polynomial.
For LWE: exponential → slightly-less-exponential. Not a fundamental break.

MLWE Security Parameters

ML-KEM comes in three variants:

For most applications: ML-KEM-768 (Level 3) is the recommended default.
NSA CNSA 2.0 requires ML-KEM-768 or higher for national security systems.

Challenge Assignment

Write a 1-page "ELI-engineer" explanation of why LWE is quantum-resistant:

1. Explain the LWE problem in 2–3 sentences using concrete numbers (not formulas)
2. Explain why Shor's algorithm doesn't apply (what periodic structure is it missing?)
3. Explain the tradeoff: LWE gives security, but at what cost vs. ECDH?
   (Key size, computation time — use the parameter table above)
4. Why is this tradeoff acceptable?

This is the kind of explanation you'll give to a colleague who asks "why are we
switching to this weird new algorithm?"

Resources

• NIST FIPS 203 §3: Mathematical background (dense but precise)
• Peikert, "A Decade of Lattice Cryptography" (2016): eprint.iacr.org/2015/939
• "An Illustrated Introduction to the BKZ Algorithm": blog post by Léo Ducas
• Dan Boneh's lattice crypto lectures (YouTube, Stanford CS355)