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 ⇒ iO
• DDH + LPN + LWE + NC1-PRG ⇒ iO
• Hash function + iO ⇒ PKE
• Hash function + iO ⇒ FE
• Hash function + iO ⇒ NIZK
• Hash function + iO ⇒ Deniable encryption
• Hash function + iO ⇒ Lossy trapdoor functions
• 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

• Hash function + iO ⇒ Deniable encryption
• Hash function + iO ⇒ DS
• Hash function + iO ⇒ FE
• Hash function + iO ⇒ Lossy trapdoor functions
• Hash function + iO ⇒ NIZK
• Hash function + iO ⇒ PKE

Produces Indistinguishability Obfuscation

• DDH + LPN + LWE + NC1-PRG ⇒ iO
• Differing-inputs obfuscation (diO) ⇔ iO
• FE ⇒ iO
• LPN + LWE + NC1-PRG ⇒ iO
• MMap ⇒ iO
• PRG in NC1 ⇒ iO