Indistinguishability Obfuscation

Indistinguishability obfuscation (iO) is a form of program obfuscation in which the obfuscated programs for any two functionally equivalent circuits are computationally indistinguishable. It is considered a “universal” cryptographic primitive: combined with one-way functions, iO implies a vast number of cryptographic primitives. The first candidate construction was given by Garg, Gentry, Halevi, Raykova, Sahai, and Waters — GGHRSW13; the first construction from well-founded assumptions was given by Jain, Lin, and Sahai — JLS21.

Syntax

An indistinguishability obfuscator $i\mathcal{O}$ is an efficient randomized algorithm such that:

• $i\mathcal{O}(1^{\lambda },C)\to \tilde{C}$, takes a circuit $C$ and outputs an obfuscated circuit $\tilde{C}$,
• $\tilde{C}(x)=C(x)$ for all inputs $x$ (functionality preservation).

Properties

Correctness

For all $\lambda \in \mathbb{N}$, circuits $C$, and inputs $x$: $i\mathcal{O}(1^{\lambda },C)(x)=C(x)$ with probability 1.

Indistinguishability

For all pairs of circuits $C_0,C_1$ of the same size that compute the same function (i.e., $C_0(x)=C_1(x)$ for all $x$), and all efficient adversaries $\mathcal{A}$:

$${\mathbf{Adv}}_{\mathcal{A}}^{i\mathcal{O}}(\lambda ):=\left|2\mathrm{Pr}\left[\mathcal{A}(i\mathcal{O}(1^{\lambda },C_b))=b\right]-1\right|$$

is negligible, where $b\stackrel{\$}{\leftarrow }\{0,1\}$.

Variations

Virtual black-box obfuscation (VBB)

A stronger notion requiring that anything an efficient adversary can compute from the obfuscated program could be computed by a simulator with only oracle access to the program. VBB obfuscation is impossible for general circuits — standard (Barak et al. 2001).

Differing-inputs obfuscation (diO)

An intermediate notion between iO and VBB, which requires indistinguishability for pairs of circuits that are hard to distinguish on any input. Known to be equivalent to iO under certain conditions.

Other results

• MMap + Leveled FHE ⇒ iO (candidate)
• SXDH + LWE + LPN + NC0-PRG ⇒ iO
• OWF + iO ⇒ PKE
• OWF + iO ⇒ FE
• OWF + iO ⇒ NIZK
• OWF + iO ⇒ Deniable encryption
• iO together with one-way functions (or close variants of them) also yields injective trapdoor functions, CCA-secure PKE and oblivious transfer — SW14
• FE ⇒ iO
• VBB obfuscation is impossible for general circuits; iO is believed to be the “best possible” general obfuscation — standard

Participates in

Builds on Indistinguishability Obfuscation

• Differing-inputs obfuscation (diO) ⇒ iO (via Differing-inputs obfuscation (diO))
• OWF + iO ⇒ Deniable encryption
• OWF + iO ⇒ DS
• OWF + iO ⇒ FE
• OWF + iO ⇒ NIZK
• OWF + iO ⇒ PKE
• OWF + iO ⇒ PPAD hardness

Produces Indistinguishability Obfuscation

• SXDH + LWE + LPN + NC0-PRG ⇒ iO
• Differing-inputs obfuscation (diO) ⇒ iO
• FE ⇒ iO
• MMap + Leveled FHE ⇒ iO