Continuous LWE is as Hard as LWE

on YouTube ↗56m

" summary

Claim: continuous LWE (CLWE) is as hard as standard LWE via a classical reduction. Proof path: use LWE leakage-resilience to convert to binary sparse secrets (norm ≈ √K), smooth discrete A to continuous A with a Gaussian preimage sampling lemma (controls noise blowup ∝ secret norm), then apply random rotations to make the secret uniform on the unit sphere. Parameter map: γ ≈ secret norm, β ≈ σ/q. Consequences: classical worst-case lattice hardness transfers to CLWE and yields new hardness for learning periodic neurons, undetectable Fourier backdoors, and mixtures of Gaussians with ≈γ components (improved from √n to n^ε or log^{1+ε} under stronger LWE assumptions).

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:27Outline
3. 0:50Learning With Errors Regev '05
4. 1:56Why care about LWE?
5. 7:41Continuous LWE [Bruna-Regev-Song-Tang '21] LWE
6. 12:44What do we know about CLWE?
7. 25:16Homogeneous CLWE (hCLWE)
8. 26:06What else does CLWE get us? Theorem (BRST 21); CLWE implies hardness of learning mixtures of Oly
9. 27:44LWE vs. CLWE
10. 34:26Our Results Theorem Gupte-V.-Vaikuntanathan "22 : New hardness for density estimation for mixtures of Gaussians in R" in poly(n) time Number of Gaussian components in mixture
11. 37:39Interpretation
12. 38:26Our Results Theorem Gupte-V.-Vaikuntanathan "22 : New hardness for density estimation for mixtures of Gaussians in R" in poly(n) times Number of Gaussian components in mixture
13. 38:59General Reduction From LWE to CLWE
14. 43:51Example: Step 2
15. 47:01Open Questions

" related talks

• 47mHardness of LWE on General Entropic DistributionsNico Döttling · Lattices: New Cryptographic Capabilities 2020
• 30mOn the Concrete Security of LWE with Small SecretLynn Chua · Lattices: Geometry, Algorithms and Hardness 2020
• 57mLattice Assumptions with Hints: Succinct LWE and its ApplicationsDavid Wu · Obfuscation
• 01h 28mThe Learning With Errors Problem and Cryptographic ApplicationsChris 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
• 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
• 37mAlgebraic Algorithms for LWELudovic Perret · The Mathematics of Modern Cryptography