Several of these candidates have been shown to achieve the strongest notion of security (virtual black-box, or VBB) against "purely algebraic" attacks in a model that we call the fully-restricted graded encoding model. In this model, each operation performed by an adversary is required to obey the algebraic restrictions of the graded encoding scheme. These restrictions essentially impose strong forms of homogeneity and multilinearity on the allowed polynomials. While important, the scope of the security proofs is limited by the stringency of these restrictions.
We propose and analyze another variant of the Garg et al. obfuscator in a setting that imposes fewer restrictions on the adversary, which we call the arithmetic setting. This setting captures a broader class of attacks than considered in previous works. We also explore connections between notions of obfuscation security and longstanding questions in arithmetic circuit complexity. Our results include the following.
(1) In the arithmetic setting where the adversary is limited to creating multilinear, but not necessarily homogenous polynomials, we obtain an unconditional proof of VBB security. This requires a substantially different analysis than previous security proofs.
(2) In the arithmetic setting where the adversary can create polynomials of arbitrary degree, we show that a proof of VBB security for any currently available candidate obfuscator would imply VP != VNP. To complement this, we show that a weaker notion of security (indistinguishability obfuscation) can be achieved unconditionally in this setting, and that VBB security can be achieved under a complexity-theoretic assumption related to the Exponential Time Hypothesis.Category / Keywords: Date: received 23 Oct 2014, last revised 1 Dec 2015 Contact author: enmiles at cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20151201:190055 (All versions of this report) Short URL: ia.cr/2014/878 Discussion forum: Show discussion | Start new discussion