Algebraic Algorithms for LWE

on YouTube ↗37m

" summary

Recasts binary-error LWE as m quadratic polynomials over Fq and shows solving by linearization requires about n^2 samples (then Gaussian elimination is polynomial). With fewer samples the attack computes a Gröbner basis; assuming semi-regularity the algebraic degree behaves like degree of regularity ≈ c·n, so complexity follows that predictable exponential/subexponential curve. Experiments up to moderate n match the semi-regular model, so asymptotic bounds are derived (standard LWE parameters remain out of reach).

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 0:40Classical LWE Problem
3. 10:43Macro Matrix
4. 13:20Semiregular sequences
5. 17:31Degree of regularity
6. 18:25Linearization bond
7. 28:14Open Questions

" related talks

• 01h 28mThe Learning With Errors Problem and Cryptographic ApplicationsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 15mAlgebraic Lattices and Ring Learning with ErrorsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 30mOn the Concrete Security of LWE with Small SecretLynn Chua · Lattices: Geometry, Algorithms and Hardness 2020
• 56mContinuous LWE is as Hard as LWENeekon Vafa · Quantum and Lattices Joint Reunion Workshop
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 57mLattice Assumptions with Hints: Succinct LWE and its ApplicationsDavid Wu · Obfuscation