Paper 2014/776

How to Obfuscate Programs Directly

Joe Zimmerman

Abstract

We propose a new way to obfuscate programs, using 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 NC1 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. 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.