Paper 2012/729
On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography
Nir Bitansky and Omer Paneth
Abstract
The traditional notion of {\em program obfuscation} requires that an obfuscation $\tilde{f}$ of a program $f$ computes the exact same function as $f$, but beyond that, the code of $\tilde{f}$ should not leak any information about $f$. This strong notion of {\em virtual blackbox} security was shown by Barak et al. (CRYPTO 2001) to be impossible to achieve, for certain {\em unobfuscatable function families}. The same work raised the question of {\em approximate obfuscation}, where the obfuscated $\tilde{f}$ is only required to approximate $\tilde{f}$; that is, $\tilde{f}$ only agrees with $f$ on some input distribution. We show that, assuming {\em trapdoor permutations}, there exist families of {\em robust unobfuscatable functions} for which even approximate obfuscation is impossible. That is, obfuscation is impossible even if the obfuscated $\tilde{f}$ only agrees with $f$ with probability slightly more than $\frac{1}{2}$, on a uniformly sampled input (below $\frac{1}{2}$agreement, the function obfuscated by $\tilde{f}$ is not uniquely defined). Additionally, we show that, assuming only oneway functions, we can rule out approximate obfuscation where $\tilde{f}$ is not allowed to err, but may refuse to compute $f$ with probability close to $1$. We then demonstrate the power of robust unobfuscatable functions by exhibiting new implications to resettable protocols that so far have been out of our reach. Concretely, we obtain a new nonblackbox simulation technique that reduces the assumptions required for resettablysound zeroknowledge protocols to {\em oneway functions}, as well as reduce roundcomplexity. We also present a new simplified construction of simultaneously resettable zeroknowledge protocols that does not rely on collisionresistent hashing. Finally, we construct a threemessage simultaneously resettable $\WI$ {\em argument of knowledge} (with a nonblackbox knowledge extractor). Our constructions are based on a special kind of ``resettable slots" that are useful for a nonblackbox simulator, but not for a resetting prover.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown status
 Keywords
 obfuscationresettable protocolsnonblackboxzeroknowledge
 Contact author(s)

nirbitan @ tau ac il
omer @ bu edu  History
 20150423: last of 6 revisions
 20130101: received
 See all versions
 Short URL
 https://ia.cr/2012/729
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/729, author = {Nir Bitansky and Omer Paneth}, title = {On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography}, howpublished = {Cryptology ePrint Archive, Paper 2012/729}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/729}}, url = {https://eprint.iacr.org/2012/729} }