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 \Theta(ls^3.64), where s is the size of the Boolean formula to be obfuscated, and l is the number of input bits to the formula. In contrast, our construction only requires the maximum number of levels of multilinearity to be \Theta(ls). This results in significant improvements in both the total size of the obfuscation, as well as 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.Category / Keywords: Date: received 26 Mar 2014, last revised 8 May 2014 Contact author: prabhanjan at cs ucla edu,divyag@cs ucla edu,yuvali@cs technion ac il,sahai@cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20140509:012221 (All versions of this report) Discussion forum: Show discussion | Start new discussion