Toward Obfuscation from Affine Determinant Programs

on YouTube ↗56m

" summary

Proposes using affine determinant programs (ADPs) as an alternative path to obfuscation, converting NC1 via branching programs and Kilian-style rerandomization into matrices whose determinant parity encodes the function; builds a recursive ADP compiler for AND/OR gates that preserves rank properties and shows a simple scalar collapse for point functions. Exposes a practical break: mod 4 recovery of error lets an attacker solve linear equations and recover added noise, breaking iO variants in polynomial time. Delivers a witness encryption from subset-sum candidate that combines a nullifying ADP with a 0/1-enforcer B (constructed by substituting Xi^2→Xi and solving linear constraints); correctness holds but overall security remains heuristic and requires larger-domain and further study.

AI-written summary · about

" chapters (6)

1. 0:00Affine determinant programs intro
2. 7:24New obfuscation motivation
3. 15:15ADP structure and properties
4. 23:58Direct obfuscation attempts
5. 38:57Witness encryption with ADPs
6. 51:15ADP security status

" related talks

• 01h 02mObfuscation IIAmit Sahai · Cryptography Boot Camp 2015
• 58mObfuscation IAmit Sahai · Cryptography Boot Camp 2015
• 31mIndistinguishability Obfuscation, Range Avoidance, and Bounded ArithmeticRahul Ilango · Proof Complexity and Meta-Mathematics 2023
• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023
• 57mIndistinguishability Obfuscation from Well-Founded AssumptionsAayush Jain · Simons Institute Workshop: New Developments in Obfuscation
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols