LPN Based IO Part 1

on YouTube ↗44m

" summary

Claims IO from four sub-exponential assumptions: LPN over Zp (error probability 1/l^delta against 2^{l^epsilon} attackers), LWE, NC0 PRGs and SXDH. Builds a new structured seed PRG whose seed splits into public and secret parts, with outputs ai, ai·s+ei (+xi) plus PRG(x). Uses LPN only to replace ai·s+ei by uniform, breaking the xi-dependency, then uses PRG security — the reduction is explicit and the SPRG meets degree-2 in secret seed and expansion targets.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 3:04Assumptions
3. 3:54What is LPN
4. 6:42Random Linear Codes
5. 8:58LPN Over ZP
6. 10:47More Details
7. 20:17Over the Wheels
8. 21:17Over Finite Fields
9. 25:02Actual Indistinguishability Property
10. 27:52Structured seed PRG
11. 38:32Other assumptions

" related talks

• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 46mIndistinguishability Obfuscation from Bilinear Maps and LPN VariantsNeekon Vafa · Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast DerandomizationEmanuele Viola, Ronen Shaltiel · ITCS 2022
• 53mFoundations 1Iftach Haitner · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 08mIncrementally Verifiable Computation for NP from Standard AssumptionsSurya Mathialagan · Proofs (Simons Institute)
• 01h 01mMPC with Silent Preprocessing via Pseuodorandom Correlation GeneratorsLisa Kohl · Lattices: New Cryptographic Capabilities 2020