Score:4

Indistinguishable Obfuscation vs Functional Encryption

br flag

What is the difference between Functional Encryption from Indistinguishable Obfuscation? Is one of them having more stronger security than the other?

Score:4
ag flag

These are equivalent primitives assuming the existence of one-way functions, which implies $\mathbf{P}\neq\mathbf{NP}$$^*$. It was shown in [G+,SW] that IO plus OWFs implies public-key FE.$^{**}$ The converse, that sub-exponentially-secure public-key FE (with some succinctness property) implies IO, was shown in [BV].

On the other hand, as pointed out in the comment by @integrator, if $\mathbf{P}=\mathbf{NP}$ then IO exists (simply pick the smallest/lexicographically-first circuit which computes the same function) but FE (which implies PKE) does not.

$^*$This was relaxed to $\mathbf{NP}\not\subseteq \mathbf{io}- \mathbf{BPP}$ in [K+].

$^{**}$[G+] assume PKE and NIZK in addition to IO. These were later shown to be implied by IO and OWFs [SW].

[BV] Bitansky and Vaikuntanathan, Indistinguishability Obfuscation from Functional Encryption, FOCS'15

[G+] Garg et al, Candidate indistinguishability obfuscation and functional encryption for all circuits, FOCS'13.

[K+] Komargodski et al, One-Way Functions and (Im)perfect Obfuscation, FOCS'14

[SW] Sahai and Waters, How to Use Indistinguishability Obfuscation: Deniable Encryption, and More, STOC'14

integrator avatar
cn flag
It's a bit of a shortcut to say they are equivalent, as other primitives such as NIZKs or PKE are used in both directions. And in fact if P=NP then iO for all circuits exists but Functional Encryption does not.
Hilder Vitor Lima Pereira avatar
us flag
[BV] says that "public-key functional encryption with succinct encryption circuits and subexponential security" implies iO. I am wondering if standard/existing FE constructions are subexponential secure and succinct...
ckamath avatar
ag flag
@integrator: True that. But whenever one talks about IO, one implicitly assumes OWFs, which implies $\mathbf{P}\neq\mathbf{NP}$, (as IO by itself is not very useful.). And IO+OWF implies PKE/NIZK (Sahai and Waters, STOC'14). Will amend the answer to make this more explicit.
ckamath avatar
ag flag
@HilderVitorLimaPereira: Good point. Will take another look at [BV].
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.