Abstract
Most recent theoretical literature on program obfuscation is based on notions
like Virtual Black Box (VBB) obfuscation and indistinguishability Obfuscation
(iO). These notions are very strong and are hard to satisfy. Further, they
offer far more protection than is typically required in practical applications.
On the other hand, the security notions introduced by software security
researchers are suitable for practical designs but are not formal or precise
enough to enable researchers to provide a quantitative security assurance.
Hence, in this paper, we introduce a new formalism for practical program
obfuscation that still allows rigorous security proofs. We believe our
formalism will make it easier to analyse the security of obfuscation schemes.
To show the flexibility and power of our formalism, we give a number of
examples. Moreover, we explain the close relationship between our formalism and
the task of providing obfuscation challenges.
This is the full version of the paper. In this version, we also give a new
rigorous analysis of several obfuscation techniques and we provide directions
for future research.