Our scheme works either with "noisy" multilinear maps, which can only evaluate expressions of degree $\lambda^c$ for pre-specified constant $c$; or with "clean" multilinear maps, which can evaluate arbitrary expressions. The "noisy" variant can be instantiated at present with the Coron-Lepoint-Tibouchi scheme, while the existence of "clean" maps is still unknown. With known "noisy" maps, our new obfuscator applies only to NC1 circuits, requiring the additional assumption of FHE in order to bootstrap to P/poly (as in other obfuscation constructions).
From "clean" multilinear maps, on the other hand (whose existence is still open), we present the first approach that would achieve obfuscation for P/poly directly, without FHE. We also introduce the concept of succinct obfuscation, in which the obfuscation overhead size depends only on the length of the input and of the secret part of the circuit. Using our new techniques, along with the assumption that factoring is hard on average, we show that "clean" multilinear maps imply succinct obfuscation for P/poly. For the first time, the only remaining obstacle to implementable obfuscation in practice is the noise growth in known, "noisy" multilinear maps. Our results demonstrate that the question of "clean" multilinear maps is not a technicality, but a central open problem.Category / Keywords: Obfuscation Date: received 30 Sep 2014, last revised 1 Oct 2014 Contact author: jzim at cs stanford edu Available format(s): PDF | BibTeX Citation Version: 20141001:214727 (All versions of this report) Short URL: ia.cr/2014/776 Discussion forum: Show discussion | Start new discussion