Welcome to the resource topic for 2014/776
Title:
How to Obfuscate Programs Directly
Authors: 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.
ePrint: https://eprint.iacr.org/2014/776
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .