Is Indistinguishability Obfuscation Real? I've recently stumbled upon an interesting Quanta Magazine article. It states that indistinguishability obfuscation (iO) 's theoretical feasibility has been proven, referencing a relatively recent paper by Jain, Lin, and Sahai. However, the Wikipedia article for iO states that the work presented in this article relies on the &quot;dubious&quot; assumption that there exists a PRNG in $NC^0$. The authors of the paper explicitly list this assumption, but what makes me stumble here is the Wikipedia article's wording. I've taken a look at the paper referenced in the Wikipedia article. I've got some base knowledge in cryptography and some more refined knowledge in complexity theory, but not enough to fully understand any of both publications. However, I've taken from glimpsing at the Applebaum paper that the question about the existence of said PRNG indirectly touches on the $P−NP$
question, making it seem to me like an unlikely-to-be-soon-settled question.
So I'm now very confused about the reliability of that Quanta Magazine article. As you've probably gathered by now, I'm not from the field of cryptography. But I took from the article that this technology (if truly feasible) could potentially revolutionize the way we think about cryptographic protocols, which makes me wonder why it didn't make bigger waves.
My question is this: Is that proof of IO reliable (i.e., can one by now safely say that IO is theoretically possible, ignoring all of the troubles of practical implementation and application), or does it stand on some for-now-unverifiable assumption?
First, the wikipedia article stated that the assumption required a PRG with an exponential stretch. This is not correct, and I have edited the article. Rather, the requirement is for a PRG in $NC_0$ with super-linear stretch (i.e., stretching from $n$ to $n^{1+\tau}$ for any $\tau&gt;0$). This is indeed not known, as far as I could ascertain from a brief search, but if you are really interested I suggest that you contact Benny Applebaum and ask him what the current status is on this question. Note that the other assumptions in the paper are also pretty strong but are just much more reasonable than everything we had until now. So, can we say that we have iO unless a lot of what we believe in crypto breaks? Probably not yet. But we are much closer to that now.
Note that the fact that the existence of something relates to P/NP and other questions does not mean anything. Almost all of crypto relies on assumptions (e.g., there is no public-key cryptography if $P=NP$). The question is only whether or not these assumptions are what we call &quot;standard&quot; or not.