Paper 2016/006

Indistinguishability Obfuscation with Non-trivial Efficiency

Huijia Lin, Rafael Pass, Karn Seth, and 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in PKC 2016
Keywords
indistinguishability obfuscation
Contact author(s)
sidtelang @ cs cornell edu
History
2016-01-04: received
Short URL
https://ia.cr/2016/006
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/006,
      author = {Huijia Lin and Rafael Pass and Karn Seth and Sidharth Telang},
      title = {Indistinguishability Obfuscation with Non-trivial Efficiency},
      howpublished = {Cryptology ePrint Archive, Paper 2016/006},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/006}},
      url = {https://eprint.iacr.org/2016/006}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.