[1] Formally, iO satisfies the property that obfuscations of two circuits of the same size which implement the same function are computationally indistinguishable.
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[3]), but with the notable exception of collision-resistant hash function families.
As measured by a 2017 paper,[needs update] 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.
[11][3] (Previously, Garg, Gentry, and Halevi (2012) had constructed a candidate version of a multilinear map based on heuristic assumptions.
[3] Finally, in 2020, Jain, Lin, and Sahai proposed a construction of iO based on the symmetric external Diffie-Helman, learning with errors, and learning plus noise assumptions,[3][5] as well as the existence of a super-linear stretch pseudorandom generator in the function class NC0.
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.[2] 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.
[2] It is useful to divide the question of the existence of iO by using Russell Impagliazzo's "five worlds",[13] which are five different hypothetical situations about average-case complexity:[6] 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,[1][3] the "crown jewel of cryptography",[3] or "crypto-complete".
[2] Concretely, an indistinguishability obfuscator (with the additional assumption of the existence of one-way functions[2]) could be used to construct the following kinds of cryptography: Additionally, if iO and one-way functions exist, then problems in the PPAD complexity class are provably hard.
[5][19] 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.