One-Way Functions and (Im)Perfect Obfuscation

摘要: A program obfuscator takes a and outputs "scrambled" version of it, where the goal is that obfuscated will not reveal much about its structure beyond what apparent from executing it. There are several ways formalizing this goal. Specifically, in indistinguishability obfuscation, first defined by Barak et al. (CRYPTO 2001), requirement results obfuscating any two functionally equivalent programs (circuits) be computationally indistinguishable. Recently, fascinating candidate construction for obfuscation was proposed Garg (FOCS 2013). This has led to flurry discovery intriguing constructions primitives protocols whose existence previously known (for instance, fully deniable encryption Sahai Waters, STOC 2014). Most them explicitly rely on additional hardness assumptions, such as one-way functions. Our get rid extra assumption. We cannot argue all polynomial-time circuits implies functions, since if P = NP, then (under notion) possible. Instead, ultimate ≠ NP possible, functions exist. main result ⊄ ioBPP there an efficient (even imperfect) obfuscator, In addition, we show (unconditionally) SZK-arguments NP. This, turn, provides alternative our result, based assumption hard-on-the average problems. To some need obfuscators simple 3CNF formulas.