You are looking at a specific version 20170604:233446 of this paper. See the latest version.

Paper 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 incrementality: small changes to the underlying program translate into small changes to the corresponding obfuscated program. We initiate a thorough investigation of 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 (according to our efficiency requirements) 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 --- namely, a weak one and a strong one. To understand the overall strength of our definitions, we formulate the notion of incremental best-possible obfuscation and show that it is equivalent to our strong 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 oblivious RAM to amplify security from weaker to stronger, while maintaining the incrementality property.

Note: Added citations

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in CRYPTO 2017
Keywords
ObfuscationIncremental Cryptography
Contact author(s)
sanjamg @ berkeley edu
omkant @ gmail com
History
2017-06-04: last of 3 revisions
2015-10-14: received
See all versions
Short URL
https://ia.cr/2015/997
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.