Succinct Obfuscation via Propositional Proofs
Surya Mathialagan
VideoAbstract:
A central line of inquiry in the study of indistinguishability obfuscation (iO) is minimizing the size of the obfuscation. Current results show how to obfuscate programs represented as Turing machines, where the size of the obfuscation depends only on the input length and not on the machine’s running time. Jain and Jin [FOCS 2022] showed how to further remove this dependency for functionally equivalent programs whose equivalence can be proven in Cook’s theory PV, assuming iO for circuits and LWE.
In this work we investigate the limits of succinct obfuscation. We focus on programs with large descriptions, where most of the description can be made public while only a portion must remain secret. To capture this setting, we put forth a new notion of fully succinct iO, where the size of the obfuscated program grows only with the size of its secret part—and not with the public part or the input length.
We give a construction of fully succinct iO whose security, like that of Jain and Jin, is restricted to programs equivalent in Cook’s theory PV. We then show how to bootstrap this construction to achieve full iO security using succinct cryptographic primitives with seemingly weaker functionality: either succinct witness encryption or SNARGs for NP with unique proofs (together with PV proofs of their correctness). Finally, we present applications of fully succinct iO, including high-rate obfuscation and succinct computational secret sharing.
Based on joint work with Abhishek Jain, Zhengzhong Jin and Omer Paneth, to appear at FOCS 2025.
Bio:
Surya is a postdoctoral researcher at NTT Research, hosted by Abhishek Jain. Prior to that, she was a PhD student at MIT under the supervision of Vinod Vaikuntanathan and Virginia Vassilevska Williams. She is broadly interested in theoretical cryptography, with a recent focus on the interplay between succinctness and proof complexity.