Thursday, May 18, 2017 at 3:00 pm in Rice 536
Committee: Mohammad Mahmoody (Advisor), David Evans (Chair), Jack Davidson, Denis Nekipelov (UVA Economics), and Sanjam Garg (UC Berkeley).
The Computational Complexity of Program Obfuscation
Recent developments in cryptography have given rise to a variety of extremely powerful tools some of which were even previously considered impossible. In this work, we focus on studying one such task called program obfuscation which, roughly speaking, is a procedure to transform a program P into an “equivalent” version Q that hides any information within the implementation of P without affecting its input/output functionality. In particular, we will study the complexity of indistinguishability obfuscation (IO) which is shown to be the “best possible” obfuscation and is versatile enough to enable a wide variety of new applications in cryptography.
Current theoretical constructions of IO rely on extremely strong and poorly understood cryptographic assumptions. Therefore basing IO on more robust and well-understood assumptions is a much desired goal. While the search for such weaker assumptions is still in progress, basing IO on standard assumptions seem out of reach.
Our main objective in this project is to see if there are inherent barriers in this regard. Namely, we aim to prove barriers between known classical, well-understood assumptions and IO. In order to prove such impossibility results on IO, we need to show that certain assumptions and/or objects are insufficient to imply IO. Traditionally, such impossibility results are proven within the “black-box framework”. However, due to the “non-black-box” nature of IO and its constructions, the existing black-box framework does not seem the right model for proving impossibility results.
We aim to first develop an extension to the black-box framework in such a way that it closely captures the type of techniques that are currently used for constructing IO. We will then use this model to prove lower bounds on the complexity of obfuscation by showing that certain assumptions and/or primitives, under this new framework, are insufficient for the construction of secure IO schemes. Furthermore, while this new extended framework facilitates a more comprehensive study of lower bounds for primitives that are currently realized from more specialized cryptographic objects, it is of independent interest and opens up the opportunity to revisit and improve upon existing well-known impossibility results.