You are looking at a specific version 20131001:183618 of this paper. See the latest version.

Paper 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}.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
ObfuscationMultilinear Maps
Contact author(s)
b @ boazbarak org
sanjamg @ cs ucla edu
yaelism @ gmail com
amitsahai @ gmail com
omerpa @ gmail com
History
2014-05-13: last of 3 revisions
2013-10-01: received
See all versions
Short URL
https://ia.cr/2013/631
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.