Obfuscation IV: A New Assumption enabling iO

on YouTube ↗42m

" summary

Conjectures that invertibility of random low‑constant‑degree polynomial systems over the integers yields iO: sample n variables, n^{1+ε} polynomials with each polynomial a sum of n^{ρ} monomials with ρ≈0.4, ±1 coefficients, and a planted integer solution with coordinates uniform in [−n,n]; give all polynomial evaluations on that solution. Degree‑4 (and other constant‑degree) cases resist gradient descent and are proven resistant to sum‑of‑squares attacks; combine this leakage with LWE samples plus tiny perturbations and assume ≤99% indistinguishability to build iO.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 1:04The Idea
3. 3:36Expanding Systems
4. 9:42Adding Complexity
5. 11:43Sampling polynomials
6. 17:14LWE
7. 17:48Assumption
8. 21:09Another distribution
9. 21:39Indistinguishability
10. 31:38How can we use this information
11. 34:35Open questions
12. 39:05Questions

" related talks

• 57mIndistinguishability Obfuscation from Well-Founded AssumptionsAayush Jain · Simons Institute Workshop: New Developments in Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 52mIndistinguishability Obfuscation via Mathematical Proofs of EquivalenceZhengzhong Jin · Proof Complexity and Meta-Mathematics 2023
• 58mObfuscation IAmit Sahai · Cryptography Boot Camp 2015
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 07mIndistinguishability Obfuscation via Mathematical ProofsZhengzhong Jin · Obfuscation
• 31mObfuscation of Probabilistic Circuits and ApplicationsHuijia Lin · Securing Computation (Simons Institute, June 2015)