Optimizing Obfuscation: Avoiding Barrington's Theorem

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