Paper 2014/878

Protecting obfuscation against arithmetic attacks

Eric Miles, Amit Sahai, and Mor Weiss

Abstract

Obfuscation, the task of compiling circuits or programs to make the internal computation unintelligible while preserving input/output functionality, has become an object of central focus in the cryptographic community. A work of Garg et al. [FOCS 2013] gave the first candidate obfuscator for general polynomial-size circuits, and led to several other works constructing candidate obfuscators. Each of these constructions is built upon another cryptographic primitive called a multilinear map, or alternatively a graded encoding scheme. 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.