Paper 2014/222

Optimizing Obfuscation: Avoiding Barrington's Theorem

Prabhanjan Ananth, Divya Gupta, Yuval Ishai, and Amit Sahai


In this work, we seek to optimize the efficiency of secure general-purpose obfuscation schemes. We focus on the problem of optimizing the obfuscation of Boolean formulas and branching programs -- this corresponds to optimizing the "core obfuscator" from the work of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013), and all subsequent works constructing general-purpose obfuscators. This core obfuscator builds upon approximate multilinear maps, where efficiency in proposed instantiations is closely tied to the maximum number of "levels" of multilinearity required. The most efficient previous construction of a core obfuscator, due to Barak, Garg, Kalai, Paneth, and Sahai (Eurocrypt 2014), required the maximum number of levels of multilinearity to be O(\ell s^{3.64}), where 's' is the size of the Boolean formula to be obfuscated, and \ell is the number of input bits to the formula. In contrast, our construction only requires the maximum number of levels of multilinearity to be roughly \ell s, or only s when considering a keyed family of formulas, namely a class of functions of the form f_z(x)=\phi(z,x) where \phi is a formula of size s. This results in significant improvements in both the total size of the obfuscation and the running time of evaluating an obfuscated formula. Our efficiency improvement is obtained by generalizing the class of branching programs that can be directly obfuscated. This generalization allows us to achieve a simple simulation of formulas by branching programs while avoiding the use of Barrington's theorem, on which all previous constructions relied. Furthermore, the ability to directly obfuscate general branching programs (without bootstrapping) allows us to efficiently apply our construction to natural function classes that are not known to have polynomial-size formulas.

Available format(s)
Publication info
Published elsewhere. MINOR revision.ACM CCS 2014
Contact author(s)
prabhanjan @ cs ucla edu
divyag @ cs ucla edu
yuvali @ cs technion ac il
sahai @ cs ucla edu
2014-09-29: last of 3 revisions
2014-03-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Prabhanjan Ananth and Divya Gupta and Yuval Ishai and Amit Sahai},
      title = {Optimizing Obfuscation: Avoiding Barrington's Theorem},
      howpublished = {Cryptology ePrint Archive, Paper 2014/222},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.