Welcome to the resource topic for 2016/006
Title:
Indistinguishability Obfuscation with Non-trivial Efficiency
Authors: Huijia Lin, Rafael Pass, Karn Seth, Sidharth Telang
Abstract:It is well known that inefficient indistinguishability obfuscators (iO) with running time poly(|C|,lambda) . 2^n, where C is the circuit to be obfuscated, lambda is the security parameter, and n is the input length of C, exists unconditionally: simply output the function table of C (i.e., the output of C on all possible inputs). Such inefficient obfuscators, however, are not useful for applications. We here consider iO with a slightly non-trivial'' notion of efficiency: the running-time of the obfuscator may still be trivial’’ (namely, poly(|C|,lambda) . 2^n), but we now require that the obfuscated code is just slightly smaller than the truth table of C (namely poly(|C|,lambda) . 2^{n(1-epsilon)}, where epsilon >0); we refer to this notion as iO with exponential efficiency, or simply exponentially-efficient iO (XiO). We show that, perhaps surprisingly, under the subexponential LWE assumption, subexponentially-secure XiO for polynomial-size circuits implies (polynomial-time computable) iO for all polynomial-size circuits.
ePrint: https://eprint.iacr.org/2016/006
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 .