International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 28 October 2014

Eric Miles, Amit Sahai, Mor Weiss
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.