We initiate a thorough investigation of {\em incremental program obfuscation}. We show that the strong simulation-based notions of program obfuscation, such as ``virtual black-box'' and ``virtual grey-box'' obfuscation, cannot be incremental even for very simple functions such as point functions. We then turn to the indistinguishability-based notions, and present two security definitions of varying strength. To understand the overall strength of our definitions, we formulate the notion of {\em incremental best-possible obfuscation} and show that it is equivalent to our (stronger) indistinguishability-based notion.
Finally, we present constructions for incremental program obfuscation satisfying both our security notions. We first give a construction achieving the weaker security notion based on the existence of general purpose indistinguishability obfuscation. Next, we present a generic transformation using {\em oblivious RAM} to amplify security from weaker to stronger, while maintaining the incrementality property.
Category / Keywords: foundations / Obfuscation, Incremental Cryptography Date: received 13 Oct 2015, last revised 15 Oct 2015 Contact author: sanjamg at berkeley edu, omkant@gmail com Available format(s): PDF | BibTeX Citation Note: Added citations Version: 20151015:175707 (All versions of this report) Short URL: ia.cr/2015/997 Discussion forum: Show discussion | Start new discussion