TY - GEN
T1 - On the impossibility of approximate obfuscation and applications to resettable cryptography
AU - Bitansky, Nir
AU - Paneth, Omer
PY - 2013
Y1 - 2013
N2 - The traditional notion of program obfuscation requires that an obfuscation P̃ of a program P computes the exact same function as P, but beyond that, the code of P̃ should not leak any information about P. This strong notion of virtual black-box security was shown by Barak et al. (CRYPTO 2001) to be impossible to achieve, for certain unobfuscatable function families. The same work raised the question of approximate obfuscation, where the obfuscated P̃ is only required to approximate P; that is, P̃ only agrees with P with high enough probability on some input distribution. We show that, assuming trapdoor permutations, there exist families of robust unobfuscatable functions for which even approximate obfuscation is impossible. Specifically, obfuscation is impossible even if the obfuscated P̃ is only required to agree with P with probability slightly more than 1 2 , on a uniformly sampled input (below 1 2 -agreement, the function obfuscated by P̃ is not uniquely defined). Additionally, assuming only one-way functions, we rule out approximate obfuscation where P̃ may output ⊥ with probability close to 1, but otherwise must agree with P. We demonstrate the power of robust unobfuscatable functions by exhibiting new implications to resettable protocols. Concretely, we reduce the assumptions required for resettably-sound zero-knowledge to one-way functions, as well as reduce round-complexity. We also present a new simplified construction of a simultaneouslyresettable zero-knowledge protocol. Finally, we construct a threemessage simultaneously-resettable witness-indistinguishable argument of knowledge (with a non-black-box knowledge extractor). Our constructions use a new non-black-box simulation technique that is based on a special kind of "resettable slots". These slots are useful for a non-black-box simulator, but not for a resetting prover.
AB - The traditional notion of program obfuscation requires that an obfuscation P̃ of a program P computes the exact same function as P, but beyond that, the code of P̃ should not leak any information about P. This strong notion of virtual black-box security was shown by Barak et al. (CRYPTO 2001) to be impossible to achieve, for certain unobfuscatable function families. The same work raised the question of approximate obfuscation, where the obfuscated P̃ is only required to approximate P; that is, P̃ only agrees with P with high enough probability on some input distribution. We show that, assuming trapdoor permutations, there exist families of robust unobfuscatable functions for which even approximate obfuscation is impossible. Specifically, obfuscation is impossible even if the obfuscated P̃ is only required to agree with P with probability slightly more than 1 2 , on a uniformly sampled input (below 1 2 -agreement, the function obfuscated by P̃ is not uniquely defined). Additionally, assuming only one-way functions, we rule out approximate obfuscation where P̃ may output ⊥ with probability close to 1, but otherwise must agree with P. We demonstrate the power of robust unobfuscatable functions by exhibiting new implications to resettable protocols. Concretely, we reduce the assumptions required for resettably-sound zero-knowledge to one-way functions, as well as reduce round-complexity. We also present a new simplified construction of a simultaneouslyresettable zero-knowledge protocol. Finally, we construct a threemessage simultaneously-resettable witness-indistinguishable argument of knowledge (with a non-black-box knowledge extractor). Our constructions use a new non-black-box simulation technique that is based on a special kind of "resettable slots". These slots are useful for a non-black-box simulator, but not for a resetting prover.
KW - Cryptography
KW - Obfuscation
KW - Resettable-cryptography
KW - Zero-knowledge
UR - http://www.scopus.com/inward/record.url?scp=84879835042&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84879835042&partnerID=8YFLogxK
U2 - 10.1145/2488608.2488639
DO - 10.1145/2488608.2488639
M3 - Conference contribution
AN - SCOPUS:84879835042
SN - 9781450320290
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 241
EP - 250
BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013
Y2 - 1 June 2013 through 4 June 2013
ER -