Our goal is to get rid of this extra assumption. We cannot argue that indistinguishability obfuscation of all polynomial-time circuits implies the existence of one-way functions, since if $P = NP$, then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if $P \neq NP$ and program obfuscation is possible, then one-way functions exist.
Our main result is that if $NP \not\subseteq ioBPP$ and there is an efficient (even imperfect) indistinguishability obfuscator, then there are one-way functions. In addition, we show that the existence of an indistinguishability obfuscator implies (unconditionally) the existence of SZK-arguments for $NP$. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the average $NP$ problems. To get some of our results we need obfuscators for simple programs such as 3CNF formulas.Category / Keywords: one-way functions, indistinguishability obfuscation Date: received 18 May 2014, last revised 20 Aug 2014 Contact author: eylony at gmail com Available format(s): PDF | BibTeX Citation Version: 20140820:084703 (All versions of this report) Discussion forum: Show discussion | Start new discussion