A beginner-friendly journey through lattices, LWE, Kyber, ECDH, and why we combine them — with interactive visualizations.
Imagine an infinite grid of dots spread out across space. In mathematics, a lattice is a regular, repetitive arrangement of points in n-dimensional space — like a crystal structure or a chessboard extended infinitely in all directions.
Formally, a lattice $\mathcal{L}$ is defined by a set of basis vectors $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_n$. Every lattice point is an integer combination of these basis vectors:
Think of a city grid. Streets run at regular intervals — that's a lattice. Every intersection is a lattice point. The block sizes define the basis vectors.
A 2D integer lattice with basis vectors b₁ (cyan) and b₂ (purple). The amber arrow shows the shortest non-zero vector — the SVP solution.
Given a lattice, find the shortest non-zero vector in it. Easy to understand, surprisingly hard to solve — especially in high dimensions.
In 2D, you can eyeball the shortest vector. But in 256 dimensions (like real Kyber uses), your intuition completely fails. The number of "candidates" grows exponentially. Even quantum computers can't solve SVP efficiently in high dimensions — this is the security foundation of lattice cryptography.
Best known algorithm (LLL + BKZ) runs in sub-exponential time. For Kyber-512 parameters, this requires ≈ 2128 operations. Infeasible.
Grover's algorithm gives a generic quadratic speedup. But for lattice problems, quantum computers provide at most a minor advantage. Still infeasible for Kyber parameters.
Given: Lattice basis $\mathbf{B} \in \mathbb{Z}^{n \times n}$
Find: $\mathbf{v} \in \mathcal{L}(\mathbf{B}) \setminus \{0\}$ with $\|\mathbf{v}\|$ minimized
Time complexity: $2^{O(n)}$ (best classical) — exponential in dimension $n$
LWE is a computational problem based on lattice hardness. Proposed by Oded Regev in 2005, it has become the cornerstone of most post-quantum cryptographic schemes.
You're given many math equations: $3x + 7y \approx 52$, $5x + 3y \approx 41$... but each equation has a small typo (error). Solving equations with known values is easy. Solving them with hidden errors, where you don't know which bits flipped, is much harder.
Given: $\mathbf{A} \in \mathbb{Z}_q^{n \times n}$ (public matrix), $\mathbf{b} \in \mathbb{Z}_q^n$ (public vector)
Hidden: $\mathbf{s} \in \mathbb{Z}_q^n$ (secret), $\mathbf{e} \in \chi^n$ (small error, $|e_i| \ll q$)
Find: $\mathbf{s}$ — This is the LWE problem. Believed to be hard even for quantum computers.
Let's work through a concrete example with tiny parameters to see LWE in action:
Public key: (A, b). Private key: s.
Given only A and b, finding s requires solving LWE — believed to be computationally infeasible for large n.
Generates A, secret s, error e. Publishes (A, b = As+e). Keeps s private.
Chooses random r and errors e₁, e₂. Computes $\mathbf{u} = \mathbf{A}^T\mathbf{r} + \mathbf{e}_1$. Her raw key: $K_A = \mathbf{b}^T\mathbf{r}$. Sends u.
Computes $K_B = \mathbf{s}^T\mathbf{u} \approx K_A$ (small error). After rounding, both have the same shared key!
$K_B = \mathbf{s}^T\mathbf{u} = \mathbf{s}^T(\mathbf{A}^T\mathbf{r} + \mathbf{e}_1) = (\mathbf{A}\mathbf{s})^T\mathbf{r} + \mathbf{s}^T\mathbf{e}_1$
$= (\mathbf{b} - \mathbf{e})^T\mathbf{r} + \mathbf{s}^T\mathbf{e}_1 = K_A - \mathbf{e}^T\mathbf{r} + \mathbf{s}^T\mathbf{e}_1$
If $|\mathbf{e}^T\mathbf{r}| + |\mathbf{s}^T\mathbf{e}_1| < q/4$: decryption succeeds ✓
Kyber (officially ML-KEM / FIPS 203) is the NIST post-quantum standard for key encapsulation. It's based on LWE structured in polynomial rings — called Module-LWE — which gives it significant performance advantages over plain LWE.
Dimension n=4 (demo), ≥ 256 in practice
Modulus q=97 (demo), large prime in practice
Dense matrix A ∈ ℤ_q^(n×n)
n=256 polynomial ring ℤ_q[x]/(xⁿ+1)
q = 3329 (prime, NTT-friendly)
Module structure: k×k matrix of polynomials
| Variant | Security | Public Key | Ciphertext | Use Case |
|---|---|---|---|---|
| Kyber-512 | ≈128-bit PQ | 800 B | 768 B | General use |
| Kyber-768 | ≈192-bit PQ | 1184 B | 1088 B | High security |
| Kyber-1024 | ≈256-bit PQ | 1568 B | 1568 B | Top secret |
| Our Demo LWE | Demo only | n=4, q=97 | 4 integers | Education |
Our interactive demo uses n=4, q=97 — tiny parameters chosen so you can see the actual numbers. This is mathematically equivalent to Kyber, just with much smaller values. Real Kyber-512 would need n=256, q=3329 and polynomial arithmetic. The key exchange logic is identical in structure.
ECDH is the most widely deployed key exchange protocol today — used in TLS 1.3, Signal, WhatsApp, and SSH. It's based on the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is hard classically but vulnerable to Shor's algorithm on quantum computers.
Alice and Bob each choose a secret color and mix it with a shared public color. They exchange their mixed colors publicly. Each then mixes the other's mixed color with their own secret — arriving at the same final color. An eavesdropper sees both mixed colors but can't determine the secret colors (the "mixing" is one-way).
Both agree on curve and generator point G (public)
Alice generates private key a, public key A = aG
Bob generates private key b, public key B = bG
Shared secret: Alice computes a·B = abG, Bob computes b·A = abG ✓
We use the browser's built-in ECDH with the NIST P-256 curve. This is the same curve used by Google, Microsoft, and Cloudflare.
y² = x³ - 3x + b (mod p)
p = 2²⁵⁶ - 2²²⁴ + 2¹⁹² + 2⁹⁶ - 1
Security: ≈128-bit classical
⚠ Quantum-vulnerable (Shor's)
We combine ECDH and LWE into a single key exchange. Both run in parallel. Their outputs are hashed together to produce the final symmetric key.
$K_{hybrid} = \text{SHA-256}(K_{ECDH} \,\|\, K_{LWE} \,\|\, \text{"HybridPQC-v1"})$
$\text{Encrypted file} = \text{AES-256-GCM}_{K_{hybrid}}(\text{plaintext, IV, AAD})$
This is the key insight. Neither ECDH alone nor LWE alone is perfect. But together, they provide defense in depth:
Mature, widely deployed, battle-tested for 20+ years
Hardware-accelerated, fast, small keys
Broken by quantum computers (Shor's algorithm, ~2030+)
Quantum-resistant under best known attacks
NIST standardized (ML-KEM / FIPS 203, 2024)
Newer — fewer years of public cryptanalysis
Gets the best of both worlds. Classical cryptographers trust ECDH. Post-quantum researchers trust LWE. Together: to break the hybrid key, an attacker must simultaneously break both — currently impossible.