# Indistinguishability Obfuscation ($$\mathcal{iO}$$)#

Definition 3

A uniform $$P P T$$ machine $$i \mathcal{O}$$ is an indistinguishability obfuscator [BGI+12] for a circuit class $$\left\{\mathcal{C}_{\lambda}\right\}$$ if the following conditions are satisfied:

• (Strong Functionality Preservation) For all security parameters $$\lambda \in \mathbb{N}^{+}$$, for all $$C \in \mathcal{C}_{\lambda}$$

$\operatorname{Pr}_{C^{\prime} \leftarrow i \mathcal{O}(\lambda, C)}\left[\forall x, C^{\prime}(x)=C(x)\right] \geq 1-\operatorname{negl}(\lambda) .$
• For any non-uniform $$P P T$$ distinguisher $$D$$, there exists a negligible function $$\alpha$$ such that the following holds: for all $$\lambda \in \mathbb{N}^{+}$$, for all pairs of circuits $$C_{0}, C_{1} \in$$ $$\mathcal{C}_{\lambda}$$, we have that if $$C_{0}(x)=C_{1}(x)$$ for all input $$x$$ and $$\left|C_{0}\right|=\left|C_{1}\right|$$ (where $$|C|$$ denotes the size of a circuit), then

$\left|\operatorname{Pr}\left[D\left(i \mathcal{O}\left(\lambda, C_{0}\right)\right)=1\right]-\operatorname{Pr}\left[D\left(i \mathcal{O}\left(\lambda, C_{1}\right)\right)=1\right]\right| \leq \alpha(\lambda)$
BGI+12

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. J. ACM, 59:6:1–6:48, 2012.