Lattice Cryptography, LWE, and the Post-Quantum¶
Job: develop the LWE (Regev), the lattice SVP/CVP, the FHE (Gentry bootstrapping), and the Kyber/Dilithium (NIST PQC) — with the Regev LWE / Gentry FHE as the worked example.
Core¶
The LWE and the Regev¶
| LWE / Regev / worst-to-average | Description |
|---|---|
| LWE | \((\mathbf{A},\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e})\) with \(\mathbf{e}\) small noise (the Regev 2005) |
| Regev | worst-case lattice \(\to\) average-case LWE (the number theory) |
The lattice and the SVP / CVP¶
| Lattice / \(\Lambda\) / SVP / CVP | Description |
|---|---|
| Lattice \(\Lambda\) | discrete subgroup of \(\mathbb{R}^n\) (the number theory) |
| SVP / CVP | shortest vector / closest vector (the number theory) |
The FHE and the Gentry¶
| FHE / Gentry / bootstrapping | Description |
|---|---|
| FHE | fully homomorphic encryption (the Gentry 2009) |
| Bootstrapping | \(\mathrm{Eval}\) homomorphic, the recrypt / bootstrapping (the Gentry) |
The Kyber / Dilithium and the NIST¶
| Kyber / MLWE / Dilithium / NIST | Description |
|---|---|
| Kyber | MLWE-based KEM (the NIST PQC) |
| Dilithium | MSIS-based signature (the NIST PQC) |
See it¶
Regev LWE and the Gentry FHE bootstrapping. The LWE: the \((\mathbf{A},\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e})\) (the \(\mathbf{e}\) the Gaussian noise, the Regev 2005, the number theory). The FHE: the Gentry the bootstrapping (the \(\mathrm{Eval}\) the homomorphic evaluation, the recrypt the refresh, the Gentry 2009). The key point: the LWE the Regev, the FHE the Gentry.
Check¶
Explain the LWE problem and the Regev worst-to-average reduction.
The LWE: the \((\mathbf{A},\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e})\) (\(\mathbf{A}\in\mathbb{Z}_q^{m\times n}\), \(\mathbf{s}\in\mathbb{Z}_q^n\) the secret, \(\mathbf{e}\in\mathbb{Z}_q^m\) the small noise). The decisional LWE: distinguish \((\mathbf{A},\mathbf{b})\) from \((\mathbf{A},\mathbf{u})\) uniform. The Regev: the worst-case GapSVP \(\to\) the average-case LWE (the quantum / classical, the number theory). So the LWE the noisy, the Regev the worst-to-average.
Explain the Gentry FHE and the bootstrapping.
The FHE: the \(\mathrm{Enc}(m)\), the \(\mathrm{Eval}(f,\mathrm{Enc}(m))=\mathrm{Enc}(f(m))\) (the homomorphic, the Gentry 2009). The bootstrapping: the noise grows, the \(\mathrm{Eval}\) the too-noisy, the recrypt / bootstrapping the refresh (the \(\mathrm{Dec}\) the homomorphic, the Gentry). The GSW: the Gentry–Sahai–Waters the FHE without bootstrapping (the number theory). So the FHE the homomorphic, the bootstrapping the refresh.
Pitfalls¶
- The LWE the noise (the \(\mathbf{e}\) the Gaussian, the Regev) — the LWE the noisy, the noise the key.
- The SVP the NP-hard (the number theory) — the SVP the hard, the approximation the lattice.
- The FHE the bootstrapping (the Gentry, the recrypt) — the FHE the bootstrapping, the GSW the without.
- The Kyber / Dilithium the NIST (the MLWE / MSIS) — the Kyber the KEM, the Dilithium the signature.
Refs¶
- Regev, "On lattices, learning with errors, random linear codes" (STOC 2005); the LWE
- Gentry, "Fully homomorphic encryption using ideal lattices" (STOC 2009); the FHE
- NIST PQC standards (2024); Kyber / Dilithium
- Gentry–Sahai–Waters, "Homomorphic encryption from learning with errors" (2013); the GSW
Next¶
Crypto index · Foundations · ZK & MPC · Hash & Signatures · Protocols & TLS · Number theory