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 of a program computes the exact same function as , but beyond that, the code of should not leak any information about . This strong notion of {\em virtual black-box} 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 is only required to approximate ; that is, only agrees with 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 only agrees with with probability slightly more than , on a uniformly sampled input (below -agreement, the function obfuscated by is not uniquely defined). Additionally, we show that, assuming only one-way functions, we can rule out approximate obfuscation where is not allowed to err, but may refuse to compute with probability close to .
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 non-black-box simulation technique that reduces the assumptions required for resettably-sound zero-knowledge protocols to {\em one-way functions}, as well as reduce round-complexity. We also present a new simplified construction of simultaneously resettable zero-knowledge protocols that does not rely on collision-resistent hashing. Finally, we construct a three-message simultaneously resettable {\em argument of knowledge} (with a non-black-box knowledge extractor). Our constructions are based on a special kind of ``resettable slots" that are useful for a non-black-box simulator, but not for a resetting prover.
@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},
url = {https://eprint.iacr.org/2012/729}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.