Indistinguishability Obfuscation via Mathematical Proofs
summary
Claims a construction of iO for unbounded-input Turing machines whose equivalence is provable in Cook's Theory PV, removing the usual 2^{input-length} security loss by verifying equivalence via short PV proofs and translating them to polynomial-size Extended Frege lines. Builds a hybrid sequence of circuits that differ only on log-size locally equivalent subcircuits and uses a new gate-by-gate topology-preserving template for iO of those local changes; security still depends on the PV proof length and standard (falsifiable) assumptions, and the reduction requires the proof.
AI-written summary · about
chapters (14)
- 0:00Proofs inside proofs
- 1:09Indistinguishability obfuscation
- 4:05Previous iO constructions
- 10:21Non-falsifiable barrier in iO
- 13:58Mathematical proofs for iO
- 17:17iO for Turing machines with PV proofs
- 28:03What PV can prove
- 31:40Techniques and Extended Frege
- 36:51Building iO by bypassing barriers
- 40:05Intermediate circuits with local changes
- 55:42iO for Turing machines
- 58:58Logic in cryptography
- 1:01:52Future directions
- 1:02:57Open questions and assumptions
related talks
52mIndistinguishability Obfuscation via Mathematical Proofs of Equivalence
31mObfuscation of Probabilistic Circuits and Applications
01h 04mTutorial on obfuscation
31mIndistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
01h 12mApplications of Obfuscation I
42mObfuscation IV: A New Assumption enabling iO
57mIndistinguishability Obfuscation from Well-Founded Assumptions
37mMutual Empowerment Between Circuit Obfuscation and Circuit Minimization