Algebraic Lattices and Ring Learning with Errors
summary
Defines Ring-LWE over integer polynomial rings, proves a quantum worst-case→average-case reduction from approximate SIVP on ideal lattices, and gives a classical search→decision reduction only for cyclotomic rings (later work gives quantum reductions to decision for any ring). Shows polynomial (NTT/FFT) multiplication drops encryption from quadratic to quasi‑linear and saves a factor of N in key/ciphertext size. Highlights practical subtleties: dual ideal RV, N-dimensional Gaussian error parameters that break spherical‑noise proofs, and reliance on quantum DGS sampling; open problems include dequantizing the reductions and relating hardness across different rings.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:00Summary
- 3:55Product Operations
- 7:55Matrix Multiplication
- 13:23Search
- 16:13Savings
- 18:15Polynomials
- 25:00Dual Ideal
- 26:25Hardness Theorems
- 30:50Ring Geometry
- 34:53Examples
- 38:58Duality
- 43:05Hardness Proof
related talks
01h 08mCryptography from Ideal Lattices
01h 40mHistorical Talk on Lattice-Based Cryptography
01h 04mThe Mathematics of Lattices II
59mNew Reductions and Algorithms for Ideal Lattices via Arakelov Random Walks
39mLattice Based Cryptography Primer
01h 08mThe Mathematics of Lattices I
38mAttacks on Ring-LWE
37mAlgebraic Algorithms for LWE