Score:1

OWF and iO Correlation

br flag

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?

Geoffroy Couteau avatar
cn flag
Note that iO still "morally" implies OWF: if NP is not contained in (infinitely often) BPP, then iO implies OWF - see [here](https://eprint.iacr.org/2014/347.pdf).
Score:4
kr flag

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

Fractalice avatar
in flag
I guess we don't know how to build PKE from OWF?
kr flag
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: https://crypto.stackexchange.com/a/83929/1423
Geoffroy Couteau avatar
cn flag
"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.
kr flag
Fair enough, I haven't followed all the recent results!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.