IACR News item: 27 March 2014
Prabhanjan Ananth, Divya Gupta, Yuval Ishai, Amit Sahai
ePrint Reportmaps, 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 $\\Theta(\\ell s^{6.82})$, 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 $\\Theta(\\ell s)$. This results in significant improvements in both the total size of the obfuscation, as well as the running time of evaluating an obfuscated formula.
Additional news items may be found on the IACR news page.