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 "dubious" 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?


1 Answer 1


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>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 "standard" or not.

  • 1
    $\begingroup$ To complete Yehuda's answer, this article (eprint.iacr.org/2018/1162) seems to be the state of the art regarding the concrete security of Goldreich's PRG, and its introduction points to several related papers. $\endgroup$ Jan 6, 2021 at 13:53
  • $\begingroup$ Okay, I think I understand: It's common in cryptography to have unproven assumptions for which there is no proof, but at least a lot of high-quality evidence. So is it that this particular assumption is more disputed than the other, presumably more classic assumptions, or was the remark in the Wikipedia article calling it a "dubious" assumption simply inappropriate? $\endgroup$ Jan 6, 2021 at 15:04
  • $\begingroup$ I think that dubious is a bit strong, but this particular assumption is not standard. So, yes, it's more disputed than classic assumptions, but dubious is a bit strong. $\endgroup$ Jan 10, 2021 at 12:34
  • $\begingroup$ If P=NP we don't have even symmetric crypto. If we can validate with the correct key in polynomial time then we can also crack without the key in polynomial time (assuming P=NP). $\endgroup$
    – Meir Maor
    Feb 2, 2021 at 15:25
  • $\begingroup$ Well, if P=NP, we have the one-time pad. We don't have symmetric encryption where the key is shorter than the message if P=NP. That is true. $\endgroup$ Feb 3, 2021 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.