AbstractsComputer Science

Program Obfuscation: Applications and Optimizations

by Divya Gupta




Institution: UCLA
Department:
Year: 2016
Keywords: Computer science; Cloud Security; Program Obfuscation
Posted: 02/05/2017
Record ID: 2113170
Full text PDF: http://www.escholarship.org/uc/item/75q380wk


Abstract

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 allowusers 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 indistinguishabilityobfuscation.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 branchingprograms - this corresponds to optimizing the ``core obfuscator'' from the work of Garg ηl, 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 naturalfunction classes that are not known to have polynomial-size formulas.