Cryptology ePrint Archive: Report 2013/631

Protecting Obfuscation Against Algebraic Attacks

Boaz Barak and Sanjam Garg and Yael Tauman Kalai and Omer Paneth and Amit Sahai

Abstract: The goal of general-purpose program obfuscation is to make an arbitrary computer program ``unintelligible'' while preserving its functionality. At least as far back as the work of Diffie and Hellman in 1976, researchers have contemplated applications of general-purpose obfuscation. However, until 2013, even heuristic constructions for general-purpose obfuscation were not known.

This changed with the work of Garg, Gentry, Halevi, Raykova, Sahai, and Waters ({FOCS 2013}), which gave the first candidate construction of general-purpose obfuscation. The heart of their construction is an obfuscator for log-depth (\textbf{NC$^1$}) circuits, building upon a simplified subset of the Approximate Multilinear Maps framework of Garg, Gentry, and Halevi ({Eurocrypt 2013}) that they call Multilinear Jigsaw Puzzles.

Given the importance of general-purpose obfuscation, it is imperative that we gain as much confidence as possible in candidates for general-purpose obfuscation. In this work, we focus on the following question: Do there exist \emph{algebraic} attacks (a.k.a. generic multilinear attacks) against candidate constructions of general-purpose obfuscation? Indeed, Garg \emph{et al.} posed the problem of proving that there exist no generic multilinear attacks against their core \textbf{NC$^1$} scheme as a major open problem in their work. Solving this problem will give us essential evidence that mathematical approaches to general purpose obfuscation introduced by Garg \emph{et al.} are sound.

This problem was first addressed in the recent work of Brakerski and Rothblum (eprint 2013), who constructed a variant of the Garg \emph{et al.} candidate obfuscator, and proved that it achieves the strongest definition of security for general-purpose obfuscation --- Virtual Black Box (VBB) security --- against all generic multilinear attacks, albeit under an unproven assumption they introduce as the Bounded Speedup Hypothesis, which strengthens the Exponential Time Hypothesis.

In this work, we resolve the open problem of Garg \emph{et al.} completely, by removing the need for this additional assumption. More specifically, we describe a different (and arguably simpler) variant of the construction of Garg \emph{et al.}, for which we can prove that it achieves Virtual Black Box security against all generic multilinear attacks, \emph{with no further assumptions}.

Category / Keywords: Obfuscation, Multilinear Maps

Date: received 1 Oct 2013, last revised 1 Oct 2013

Contact author: b at boazbarak org, sanjamg@cs ucla edu, yaelism@gmail com, amitsahai@gmail com, omerpa@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20131001:183618 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]