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^2s^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 NC

$$^1$$

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.