5
$\begingroup$

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

$\endgroup$

1 Answer 1

5
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – integrator
    Commented Sep 2, 2021 at 12:53
  • $\begingroup$ [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... $\endgroup$ Commented Sep 2, 2021 at 13:16
  • $\begingroup$ @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. $\endgroup$
    – ckamath
    Commented Sep 2, 2021 at 14:43
  • $\begingroup$ @HilderVitorLimaPereira: Good point. Will take another look at [BV]. $\endgroup$
    – ckamath
    Commented Sep 2, 2021 at 15:16

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.