How to Obfuscate Programs Directly

We propose a new way to obfuscate programs, via composite-order multilinear maps. Our construction operates directly on straight-line programs (arithmetic circuits), rather than converting them to matrix branching programs as in other known approaches. This yields considerable efficiency improvements. For an NC 1 circuit of size s and depth d, with n inputs, we require only O(d(2)s(2) + n(2)) multilinear map operations to evaluate the obfuscated circuit-as compared with other known approaches, for which the number of operations is exponential in d. We prove virtual black-box (VBB) security for our construction in a generic model of multilinear maps of hidden composite order, extending previous models for the prime-order setting. 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. With 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. Our construction is efficient enough that if clean multilinear maps were known, then general-purpose program obfuscation could become implementable in practice. Our results demonstrate that the question of clean multilinear maps is not a technicality, but a central open problem.