Hardness of LWE on General Entropic Distributions
summary
Shows hardness of LWE when the secret comes from a general min-entropy distribution by introducing gentle flooding and a new quantity noise loss (eNOS), which measures average conditional min-entropy of s given s+e. Key technical tool is a Gaussian decomposition e = e1 F + e2 so part of the noise “floods” the secret, letting a leftover-hash style argument replace s by uniform under entropy bounds roughly K log Q plus about n log Q / Sigma. Gives tighter requirements for ball-bounded secrets, matching attacks for composite moduli, and a black-box impossibility result.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:20Leakage Resilient Cryptogram
- 1:10Overview
- 2:12Learning with Errors Rego
- 5:52LWE-based Crypto
- 8:05Leakage Resilience on Assumption Level
- 11:41Hardness LWE with Entropic Sec
- 16:37The Lossiness Technique GKP
- 21:26Our Approach
- 27:39From Noise-Lossiness to Hardness of Entre LWE
- 35:32Parameters
- 36:47Noise Lossiness: General Distribut
- 39:08Noise Lossiness: Short Distribute
- 40:17Main Result
- 42:20Lower Bounds
- 43:10Counterexample
- 44:19BB-Lower Bound
related talks
56mContinuous LWE is as Hard as LWE
01h 28mThe Learning With Errors Problem and Cryptographic Applications
30mOn the Concrete Security of LWE with Small Secret
56miO via Functional Encryption: Techniques and Challenges from LWE
01h 07mLattices and Encrypted Computation
01h 04mThe Mathematics of Lattices II
37mAlgebraic Algorithms for LWE
57mLattice Assumptions with Hints: Succinct LWE and its Applications