In cryptography, indistinguishability obfuscation (abbreviated IO or iO) is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot be distinguished from each other. Informally, such obfuscation hides the implementation of a program while still allowing users to run it. Formally, iO satisfies the property that obfuscations of two circuits of the same size which implement the same function are computationally indistinguishable. Indistinguishability obfuscation has several interesting theoretical properties. Firstly, iO is the "best-possible" obfuscation (in the sense that any secret about a program that can be hidden by any obfuscator at all can also be hidden by iO). Secondly, iO can be used to construct nearly the entire gamut of cryptographic primitives, including both mundane ones such as public-key cryptography and more exotic ones such as deniable encryption and functional encryption (which are types of cryptography that no-one previously knew how to construct), but with the notable exception of collision-resistant hash function families. For this reason, it has been referred to as "crypto-complete". Lastly, unlike many other kinds of cryptography, indistinguishability obfuscation continues to exist even if P=NP (though it would have to be constructed differently in this case), though this does not necessarily imply that iO exists unconditionally. Though the idea of cryptographic software obfuscation has been around since 1996, indistinguishability obfuscation was first proposed by Barak et al. (2001), who proved that iO exists if P=NP is the case. For the P≠NP case (which is harder, but also more plausible), progress was slower: Garg et al. (2013) proposed a construction of iO based on a computational hardness assumption relating to multilinear maps, but this assumption was later disproven. A construction based on "well-founded assumptions" (hardness assumptions that have been well-studied by cryptographers, and thus widely assumed secure) had to wait until Jain, Lin, and Sahai (2020). (Even so, one of these assumptions used in the 2020 proposal is not secure against quantum computers.) Currently known indistinguishability obfuscation candidates are very far from being practical. As measured by a 2017 paper, even obfuscating the toy function which outputs the logical conjunction of its thirty-two Boolean data type inputs produces a program nearly a dozen gigabytes large.
Formal definition
Let i O {\displaystyle {\mathcal {iO}}} be some uniform probabilistic polynomial-time algorithm. Then i O {\displaystyle {\mathcal {iO}}} is called an indistinguishability obfuscator if and only if it satisfies both of the following two statements:
Completeness or Functionality: For any Boolean circuit C of input length n and input x ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} , we have Pr [ C ′ ( x ) = C ( x ) : C ′ ← i O ( C ) ] = 1. {\displaystyle \Pr[C'(x)=C(x):C'\leftarrow {\mathcal {iO}}(C)]=1.}
Indistinguishability: For every pair of circuits C 0 , C 1 {\displaystyle C_{0},C_{1}} of the same size k that implement the same functionality, the distributions { i O ( C 0 ) } {\displaystyle \{{\mathcal {iO}}(C_{0})\}} and { i O ( C 1 ) } {\displaystyle \{{\mathcal {iO}}(C_{1})\}} are computationally indistinguishable. In other words, for any probabilistic polynomial-time adversary A, there is a negligible function ε ( k ) {\displaystyle \varepsilon (k)} (i.e., a function that eventually grows slower than 1 / p ( k ) {\displaystyle 1/p(k)} for any polynomial p) such that, for every pair of circuits C 0 , C 1 {\displaystyle C_{0},C_{1}} of the same size k that implement the same functionality, we have | Pr [ A ( i O ( C 0 ) ) = 1 ] − Pr [ A ( i O ( C 1 ) ) = 1 ] | ≤ ε ( k ) . {\displaystyle |\Pr[A({\mathcal {iO}}(C_{0}))=1]-\Pr[A({\mathcal {iO}}(C_{1}))=1]|\leq \varepsilon (k).}
… excerpt ends here. Continue reading the full article.
