The Computational Complexity of Program Obfuscation

Recent developments in cryptography have given rise to a variety of tools that allow for secure communication and computation of data. In this work we focus on studying one such task called program obfuscation which, roughly speaking, hides any information within a program's code without affecting its functionality. In particular, we will study the complexity of the main variant of obfuscation called indistinguishability obfuscation (IO), which is itself versatile enough to enable a wide variety of new applications in cryptography, and our main objective is determine a lower bound on the assumptions required for realizing an IO scheme.

The reason behind pursuing this objective of proving such lower bounds for IO (and in general for any other cryptographic primitive) is to understand the complexity of said primitive and to investigate whether it is possible to use well-studied assumptions to base this primitive on. In order to prove these kinds of lower bounds for IO, we need to show that certain assumptions and/or objects are insufficient to achieve it. Such classes of impossibility results are proven under the "black-box framework" introduced by Impagliazzo and Rudich in 1989 and later formalized by Reingold, Trevisan, and Vadhan in 2004. However, due to the nature of current IO constructions, the existing techniques for proving impossibility results are not conducive to ruling out the type of "complex" assumptions on which IO stands.

The goal of this thesis is to first develop new techniques and propose extensions to the aforementioned classical black-box framework, allowing us to rule out some natural primitives from being able to construct IO. This then allows us to explore and prove lower bounds on the complexity of obfuscation by showing that certain assumptions and/or primitives, under this newly developed paradigm, are insufficient for the construction of secure IO schemes. In particular, we rule out constructions of IO from both various traditional long-established primitives and some of the more recent advanced objects. Furthermore, while this new extended framework facilitates a more comprehensive study of lower bounds for recent sophisticated 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 even the existing well-known impossibility results.