Program Obfuscation: Applications and Optimizations
- Author(s): Gupta, Divya
- Advisor(s): Sahai, Amit
- et al.
Recently, candidate constructions were given for indistinguishability obfuscation by Garg, Gentry, Halevi, Raykova, Sahai, and Waters [FOCS'13]. The goal of general-purpose program obfuscation is to make an arbitrary computer program ``unintelligible'' while preserving its functionality. Since then, this new tool has been used to obtain many new applications. In this dissertation, we study the problem of protecting software against new and powerful adversary structures as well as optimize the efficiency of secure general-purpose obfuscation schemes.
In the first part of this dissertation, we initiate the study of hosting services on an untrusted cloud. Specifically, we consider a scenario where a service provider has created a software service S and desires to outsource the execution of this service to an untrusted cloud. The software service contains secrets that the provider would like to keep hidden from the cloud. For example, the software might contain a secret database, and the service could allow
users to make queries to different slices of this database depending on the user's identity. Furthermore, we seek to protect knowledge of the software S to the maximum extent possible even if the cloud can collude with several corrupted users. We provide the first formalizations of security for this setting, and construction relying on indistinguishability
The great interest in the utility of obfuscation leads to a natural and pressing goal: to improve the efficiency of general-purpose obfuscation. In the second part of this dissertation, we initiate the work to optimize the efficiency of secure general-purpose obfuscation schemes.
We focus on the problem of optimizing the obfuscation of Boolean formulas and branching
programs - this corresponds to optimizing the ``core obfuscator'' from the work of Garg \etal, and all subsequent works constructing general-purpose obfuscators. Our efficiency improvement is obtained by generalizing the class of branching programs that can be directly obfuscated. This generalization allows us to achieve a simple simulation of formulas by branching programs while avoiding the use of Barrington's theorem, on which all previous constructions relied. Furthermore, the ability to directly obfuscate general branching programs (without bootstrapping) allows us to efficiently apply our construction to natural
function classes that are not known to have polynomial-size formulas.