Cryptology ePrint Archive: Report 2014/878

Protecting obfuscation against arithmetic attacks

Eric Miles and Amit Sahai and Mor Weiss

Abstract: Recently, the work of Garg et al. (FOCS 2013) gave the first candidate general-purpose obfuscator. This construction is built upon multilinear maps, also called a graded encoding scheme. Several subsequent works have shown that variants of this obfuscator achieves the highest notion of security (VBB security) against "purely algebraic" attacks, namely attacks that respect the restrictions of the graded encoding scheme. While important, the scope of these works is somewhat limited due to the strong restrictions imposed on the adversary.

We propose and analyze another variant of the Garg et al. obfuscator in a setting that imposes fewer restrictions on the adversary that we call the arithmetic setting. This setting captures a broader class of algebraic attacks than considered in previous works. Most notably, it allows for unlimited additions across different "levels" of the encoding. In this setting, we present two results:

- First, in the arithmetic setting where the adversary is limited to creating only multilinear polynomials, we obtain an unconditional proof of VBB security.

- Second, in the arithmetic setting where the adversary can create polynomials of arbitrary degree, we prove VBB security under an assumption that is closely related to the Bounded Speedup Hypothesis of Brakerski and Rothblum (TCC 2014). We also give evidence that any unconditional proof of VBB security in this model would entail proving the algebraic analog of P \neq NP.

Category / Keywords:

Date: received 23 Oct 2014, last revised 2 Mar 2015

Contact author: enmiles at cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20150302:233335 (All versions of this report)

Short URL: ia.cr/2014/878

Discussion forum: Show discussion | Start new discussion