1
$\begingroup$

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?

$\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$ Oct 21, 2021 at 14:49

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ I guess we don't know how to build PKE from OWF? $\endgroup$
    – Fractalice
    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$ 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$ Oct 21, 2021 at 14:45
  • $\begingroup$ Fair enough, I haven't followed all the recent results! $\endgroup$ Oct 21, 2021 at 15:26

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.