Path: blob/main/frontier/08-lattices-post-quantum/README.md
483 views
Module 08: Lattices and Post-Quantum Cryptography
The geometry of integer grids, and why quantum computers can't break them.
Prerequisites
Module 01: Modular Arithmetic (modular reduction, congruences, and arithmetic in Z_n)
Linear algebra familiarity (bases, linear independence, inner products)
Learning Objectives
After completing this module you will:
Understand lattice bases, the shortest vector problem (SVP), and the closest vector problem (CVP)
Apply the LLL algorithm to reduce a lattice basis and break weak schemes
Grasp the Learning With Errors (LWE) and Ring-LWE hardness assumptions
See how Kyber/ML-KEM works at a high level and why it resists quantum attack
Explore (SageMath Notebooks)
Work through these notebooks in order:
| # | Notebook | What You'll Learn |
|---|---|---|
| a | Lattices and Bases | What a lattice is, how different bases span the same lattice, visualizing in 2D |
| b | Shortest Vector Problem | Why finding short vectors is hard, and how SVP/CVP relate to cryptography |
| c | LLL Algorithm | Step by step LLL basis reduction with animated lattice plots |
| d | Learning With Errors | The LWE problem: hiding secrets in noisy linear equations |
| e | Ring-LWE | Adding polynomial ring structure for efficiency |
| f | Kyber Overview | End to end walkthrough of ML-KEM key encapsulation |
Implement (Rust)
Build these from scratch in rust/src/lib.rs:
| # | Function | Description |
|---|---|---|
| 1 | gram_schmidt_2d | Compute the Gram-Schmidt orthogonalization of a 2D lattice basis |
| 2 | lll_reduce_2d | Run LLL basis reduction on a 2D lattice |
| 3 | lwe_keygen | Generate an LWE public/private key pair with error sampling |
| 4 | lwe_encrypt | Encrypt a single bit under an LWE public key |
| 5 | lwe_decrypt | Decrypt an LWE ciphertext using the secret key |
Run: cargo test -p lattices-pq
Break
Try these attacks in the break/ folder:
LLL attack on a low dimension lattice scheme. Use basis reduction to recover the secret key when the lattice dimension is too small.
Recover LWE secret with no noise. Observe how removing the error term makes LWE trivially solvable via Gaussian elimination.
Connect
See where this shows up in practice (in the connect/ folder):
NIST PQC standards. ML-KEM (Kyber) for key encapsulation and ML-DSA (Dilithium) for digital signatures are the first post-quantum standards.
Hybrid TLS with post-quantum. Chrome and Cloudflare already deploy X25519+ML-KEM hybrid key exchange to hedge against quantum threats.