Cryptology ePrint Archive: Report 2015/997

Incremental Program Obfuscation

Sanjam Garg and Omkant Pandey

Abstract: Recent advances in program obfuscation suggest that it is possible to create software that can provably safeguard secret information. However, software systems usually contain large executable code that is updated multiple times and sometimes very frequently. Freshly obfuscating the program for every small update will lead to a considerable efficiency loss. Thus, an extremely desirable property for obfuscation algorithms is {\em incrementality}: small changes to the underlying program translate into small changes to the corresponding obfuscated program.

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 Sep 2016

Contact author: sanjamg at berkeley edu, omkant@gmail com

Available format(s): PDF | BibTeX Citation

Note: Added citations

Version: 20160915:202739 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]