Welcome to the resource topic for 2013/557
Title:
Black-Box Obfuscation for d-CNFs
Authors: Zvika Brakerski, Guy N. Rothblum
Abstract:We show how to securely obfuscate a new class of functions: {\em conjunctions of NC0_d circuits}. These are functions of the form C(x) = \bigwedge_{i=1}^m C_i(x), where each C_i is a boolean NC0_d circuit, whose output bit is only a function of d = O(1) bits of the input x. For example, d-CNFs, where each clause is a disjunction of at most d variables, are in this class. Given such a function, we produce an obfuscated program that preserves the input-output functionality of the given function, but reveals nothing else. Our construction is based on multilinear maps, and can be instantiated using the recent candidates proposed by Garg, Gentry and Halevi (EUROCRYPT 2013) and by Coron, Lepoint and Tibouchi (CRYPTO 2013). We prove that the construction is a secure obfuscation in a generic multilinear group model, under the black-box definition of Barak et al.\ (CRYPTO 2001). Security is based on a new {\em worst-case} hardness assumption about exponential hardness of the NP-complete problem 3-SAT, the {\em Bounded Speedup Hypothesis}. One of the new techniques we introduce is a method for enforcing input consistency, which we call {\em randomizing sub-assignments}. We hope that this technique can find further application in constructing secure obfuscators. The family of functions we obfuscate is considerably richer than previous works that consider black-box obfuscation. As one application, we show how to achieve {\em obfuscated functional point testing}: namely, to construct a circuit that checks whether f(x)=y, where f is an arbitrary public'' polynomial-time computable function, but $y$ is a secret’’ point that is hidden in the obfuscation.
ePrint: https://eprint.iacr.org/2013/557
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 .