OWF + iO ⇒ FE

Free reduction · standard model · GGHRSW13, SW14 · security loss: polynomial: a constant number of PKE and NIZK hybrids, and one iO hybrid per functional key each time the keys switch the component they decrypt

Statement

If iO for all polynomial-size circuits and a one-way function exist, there is a selectively secure, indistinguishability-based functional encryption scheme for all polynomial-size circuits: for all efficient $\mathcal{A}$ that announce $(m_0,m_1)$ before seeing the public parameters and request functional keys only for circuits $f$ with $f(m_0)=f(m_1)$, the advantage in distinguishing an encryption of $m_0$ from one of $m_1$ is negligible. GGHRSW13 build the scheme from iO, PKE and a statistically simulation-sound NIZK, and SW14 build the latter two from iO and one-way functions.

Sketch

A ciphertext is two PKE encryptions of $m$ with a statistically simulation-sound NIZK proof that both encrypt the same message, and the functional key for $f$ obfuscates the program that verifies the proof, decrypts one component and outputs $f(m)$. Security is a Naor–Yung-style hybrid in which iO switches the component the functional key decrypts, the two programs being functionally equivalent by statistical simulation soundness and $f(m_0)=f(m_1)$.