Known results regarding the (Im)possibility of Obfuscating Programs are typically viewed as bad news: Obfuscating Programs has numerous appealing appications and many of theme are either ruled out by the aforementioned impossibility results or are shown to be unachievable via a direct reduction to Program Obfuscation. The current papers show that these impossibility results have positive implications.
The first paper of Bitansky and Paneth uses the existence of unobfuscatable functions (i.e., a strong form of such an impossiblity result) to present constructions of resettable-sound ZK arguments that avoid Barak's non-black-box zero-knowledge agruments. Their second paper proves the existence of stronger forms of unobfuscatable functions (based on various standard assumptions), and uses these stronger primitives to derive further results regarding "resettable cryptography".
1. From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique [FOCS 2012]
The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak's techniques were subsequently extended and have given rise to various powerful applications.
We present the first non-black-box simulation technique that does not rely on Barak's technique (or on non-standard assumptions). Our technique is based on essentially different tools: it does not invoke universal arguments, nor does it rely on collision-resistant hashing. Instead, the main ingredient we use is the impossibility of general program obfuscation (Barak et al., CRYPTO 2001).
Using our technique, we construct a new resettably-sound zero-knowledge (rsZK) protocol. rsZK protocols remain sound even against cheating provers that can repeatedly reset the verifier to its initial state and random tape. Indeed, for such protocols black-box simulation is impossible. Our rsZK protocol is the first to be based solely on semi-honest oblivious transfer and does not rely on collision-resistant hashing, in addition, our protocol does not use PCP machinery.
In the converse direction, we show a generic transformation from any rsZK protocol to a family of functions that cannot be obfuscated.
2. On the impossibility of approximate obfuscation and applications to resettable cryptography [STOC 2013]
The traditional notion of *program obfuscation* requires that an obfuscation ObfProg of a program Prog computes the exact same function as Prog, but beyond that, the code of ObfProg should not leak any information about Prog. 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 ObfProg is only required to approximate Prog; that is, ObfProg only agrees with Prog 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 ObfProg is only required to agree with Prog with probability slightly more than 1/2, on a uniformly sampled input (below 1/2-agreement, the function obfuscated by ObfProg is not uniquely defined). Additionally, assuming only one-way functions, we rule out approximate obfuscation where ObfProg may output bot with probability close to $1$, but otherwise must agree with Prog.
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 simultaneously-resettable zero-knowledge protocol. Finally, we construct a three-message 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.