The Learning With Errors Problem and Cryptographic Applications
summary
Defines LWE with modulus q (typically polynomial in n) and Gaussian error (std ≈ √n), proves a quantum worst-case to average-case reduction from GapSVP/SIVP (approx factor ≈ n/α) and a separate classical reduction from GapSVP with worse parameters, and uses tools like discrete Gaussian trapdoor sampling and randomized nearest-plane rounding (Gram–Schmidt lengths < σ). Constructions: Regev-style CPA PKE, CCA variants, SIS-based signatures via oblivious Gaussian sampling, identity-based encryption from trapdoor key extraction, and FHE that still needs circular security; several open problems remain.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:06Short integer solution
- 12:00LWE
- 12:35Search
- 16:07Decision
- 17:04Quantum Reduction
- 21:06Lattice
- 23:57Summary
- 25:55Cryptographic Applications
- 39:10Digital Signatures
- 43:10Security
- 45:09Trapdoors
- 45:42Exercise Break
