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 every polynomial $s$, every pair of circuit families $\{C_{0,\lambda }{\}}_{\lambda },\{C_{1,\lambda }{\}}_{\lambda }$ with $|C_{0,\lambda }|=|C_{1,\lambda }|\le s(\lambda )$ and $C_{0,\lambda }(x)=C_{1,\lambda }(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,\lambda }))=b\right]-1\right|$$

is negligible, where $b\stackrel{\$}{\leftarrow }\{0,1\}$ — GGHRSW13. The circuits grow with $\lambda$: for one fixed pair, the obfuscator that outputs a canonical truth table once $\lambda$ exceeds the pair’s truth-table size, and the circuit itself before, has advantage eventually $0$ yet hides nothing — standard.

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 — BGI+01.

Sub-exponentially secure iO

iO is sub-exponentially secure if there is a constant $\epsilon >0$ such that every adversary of size $2^{{\lambda }^{\epsilon }}$ has advantage at most $2^{-{\lambda }^{\epsilon }}$ in the indistinguishability game. Trapdoor permutations from iO — BPW16 — and fully homomorphic encryption without circular security — CLTV15 — assume it.

Statistical iO

An efficient, perfectly correct obfuscator $i\mathcal{O}$ is statistically secure if for all circuit families as in the indistinguishability game, the distributions $i\mathcal{O}(1^{\lambda },C_{0,\lambda })$ and $i\mathcal{O}(1^{\lambda },C_{1,\lambda })$ are within negligible statistical distance — GR07. Statistical iO is iO, but it does not exist even for 3-CNF formulas unless the polynomial hierarchy collapses to its second level (No reduction from iO to statistical iO) — GR07.

Differing-inputs obfuscation (diO)

A differing-inputs obfuscator requires that for every efficient sampler of $(C_0,C_1,aux)$ with $|C_0|=|C_1|$ such that no efficient algorithm given $(C_0,C_1,aux)$ finds $x$ with $C_0(x)\ne C_1(x)$ except with negligible probability, $(C_0,C_1,aux,i\mathcal{O}(1^{\lambda },C_0))$ and $(C_0,C_1,aux,i\mathcal{O}(1^{\lambda },C_1))$ are computationally indistinguishable — BCP14. Functionally equivalent circuits have no differing input, so diO implies iO — standard. iO implies diO for circuit pairs that differ on polynomially many inputs — BCP14 — and diO for general auxiliary input is implausible — GGHW14.

Other results

• MMap + Leveled FHE ⇒ iO (candidate)
• Sub-exponential SXDH + LWE + LPN + NC0-PRG ⇒ iO
• OWF + iO ⇒ PKE
• OWF + iO ⇒ FE
• OWF + iO ⇒ Non-adaptively sound NIZK argument
• 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 — BGI+01; efficient iO is best-possible obfuscation: it leaks no more than any other circuit of comparable size computing the same function — GR07

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 ⇒ Non-adaptively sound NIZK argument
• OWF + iO ⇒ PKE
• iO + NP ⊄ io-BPP ⇒ OWF
• iO + OWF ⇒ Multiparty NIKE (Boneh–Zhandry)
• iO + OWP ⇒ CLS hardness
• iO + OWP ⇒ PPAD hardness
• iO ⇒ Statistical ZK arguments for NP
• iO ⇒ Witness encryption
• Statistical iO ⇒ iO (via Statistical iO)
• Sub-exponential OWF + iO ⇒ PPAD hardness (via Sub-exponentially secure iO)
• Sub-exponential iO + Sub-exponential OWF ⇒ TDP (Bitansky–Paneth–Wichs) (via Sub-exponentially secure iO)
• Sub-exponential iO + Rerandomizable encryption ⇒ Compact FHE (CLTV) (via Sub-exponentially secure iO)
• Sub-exponentially secure iO ⇒ iO (via Sub-exponentially secure iO)

Produces Indistinguishability Obfuscation

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

Barriers

• No fully-black-box reduction from iO + OWF to domain-invariant OWP
• No fully-black-box reduction from iO + OWP to CRHF
• No fully-black-box reduction from iO + OWP to average-case-hard SZK
• No reduction from iO to statistical iO