What is the relationship between one way functions(OWF) and indistinguishable obfuscation(iO)? I know that iO exists even when P=NP and OWF don't exist. But does the existence of OWF imply iO?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Note that iO still "morally" implies OWF: if NP is not contained in (infinitely often) BPP, then iO implies OWF - see here. $\endgroup$– Geoffroy CouteauCommented Oct 21, 2021 at 14:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
We don't know of any construction of iO from one-way functions[*], and it would be highly surprising if such a thing existed. Indeed, iO + OWF implies public-key encryption (and various other “cryptomania” primitives), so if OWF alone implied iO, it would also imply PKE.
[*] At this point in time, we don't know of any construction of iO from standard assumptions, period, as far as I know (see Geoffroy's comment below).
-
$\begingroup$ I guess we don't know how to build PKE from OWF? $\endgroup$ Commented Oct 21, 2021 at 7:36
-
1$\begingroup$ Yes, and I we have good reasons to think that such a construction shouldn't exist. For example, a black-box construction is known to be impossible, and even some classes of non-black-box constructions have been ruled out. See e.g. this reply: crypto.stackexchange.com/a/83929/1423 $\endgroup$ Commented Oct 21, 2021 at 12:59
-
4$\begingroup$ "At this point in time, we don't know of any construction of iO from standard assumptions, period, as far as I know" I disagree, we now have constructions of iO from perfectly fine assumptions: subexponential LPN over large fields + subexponential hardness of Goldreich PRG + subexponential SXDH. All are old, well studied, highly plausible assumptions that I would call standard. $\endgroup$ Commented Oct 21, 2021 at 14:45
-
$\begingroup$ Fair enough, I haven't followed all the recent results! $\endgroup$ Commented Oct 21, 2021 at 15:26