IACR News item: 04 January 2016
Huijia Lin, Rafael Pass, Karn Seth, Sidharth Telang
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.