Welcome to the resource topic for 2012/729
Title:
On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography
Authors: Nir Bitansky, 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 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 \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 one-way 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 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 \WI {\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.
ePrint: https://eprint.iacr.org/2012/729
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 .