Indistinguishability obfuscation

Let \mathcal{iO} be some uniform probabilistic polynomial-time algorithm. Then \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\in\{0, 1\}^n, we have \Pr[C'(x) = C(x): C' \leftarrow\mathcal{iO}(C) ] = 1. • Indistinguishability: For every pair of circuits C_0, C_1 of the same size k that implement the same functionality, the distributions \{\mathcal{iO}(C_0)\} and \{\mathcal{iO}(C_1)\} are computationally indistinguishable. In other words, for any probabilistic polynomial-time adversary A, there is a negligible function \varepsilon(k) (i.e., a function that eventually grows slower than 1/p(k) for any polynomial p) such that, for every pair of circuits C_0, C_1 of the same size k that implement the same functionality, we have|\Pr[A(\mathcal{iO}(C_0))=1] - \Pr[A(\mathcal{iO}(C_1))=1]|\leq\varepsilon(k). == History ==

In 2001, Barak et al., showing that black-box obfuscation is impossible, also proposed the idea of an indistinguishability obfuscator, and constructed an inefficient one. Although this notion seemed relatively weak, Goldwasser and Rothblum (2007) showed that an efficient indistinguishability obfuscator would be a best-possible obfuscator, and any best-possible obfuscator would be an indistinguishability obfuscator. (However, for inefficient obfuscators, no best-possible obfuscator exists unless the polynomial hierarchy collapses to the second level. Candidate constructions Barak et al. (2001) proved that an inefficient indistinguishability obfuscator exists for circuits; that is, the lexicographically first circuit that computes the same function. (Previously, Garg, Gentry, and Halevi (2012) had constructed a candidate version of a multilinear map based on heuristic assumptions.) Starting from 2016, Lin began to explore constructions of iO based on less strict versions of multilinear maps, constructing a candidate based on maps of degree up to 30, and eventually a candidate based on maps of degree up to 3. as well as the existence of a super-linear stretch pseudorandom generator in the function class NC0.) It is possible that this construction could be broken with quantum computing, but there is an alternative construction that may be secure even against that (although the latter relies on less established security assumptions). Practicality There have been attempts to implement and benchmark iO candidates. In 2017, an obfuscation of the function x_1\wedge x_2\wedge \dots \wedge x_{32} at a security level of 80 bits took 23.5 minutes to produce and measured 11.6 GB, with an evaluation time of 77 ms. Additionally, an obfuscation of the Advanced Encryption Standard encryption circuit at a security level of 128 bits would measure 18 PB and have an evaluation time of about 272 years. == Existence ==

It is useful to divide the question of the existence of iO by using Russell Impagliazzo's "five worlds", which are five different hypothetical situations about average-case complexity: • Algorithmica: In this case P = NP, but iO exists. • Heuristica: In this case NP problems are easy on average; iO does not exist. • Pessiland: In this case, BPP ≠ NP, but one-way functions do not exist; as a result, iO does not exist. • Minicrypt: In this case, one-way functions exist, but secure public-key cryptography does not; iO does not exist (because explicit constructions of public-key cryptography from iO and one-way functions are known). • Cryptomania: In this case, secure public-key cryptography exists, but iO does not exist. • Obfustopia: In this case, iO is believed to exist. == Potential applications ==

Indistinguishability obfuscators, if they exist, could be used for an enormous range of cryptographic applications, so much so that it has been referred to as a "central hub" for cryptography, • IND-CCA-secure public-key cryptography • Short digital signatures However, indistinguishability obfuscation cannot be used to construct every possible cryptographic protocol: for example, no black-box construction can convert an indistinguishability obfuscator to a collision-resistant hash function family, even with a trapdoor permutation, except with an exponential loss of security. == See also ==