Optimizing obfuscation: Avoiding Barrington’s theorem. Cryptology ePrint Archive, Report 2014/222, Version 20140329:175740, 2014. https: //eprint.iacr.org/2014/222

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, Gen-try, 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(`s3.64), where s is the size of the Boolean formula to be obfuscated, and ` 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 `s, or only s when considering a keyed family of formulas, namely a class of functions of the form fz(x) = φ(z, x) where φ is a formula of size s. This results in significant improvements in both the total size of the obfuscation and the runnin