Indistinguishability obfuscation

This article may be too technical for most readers to understand. Please to make it understandable to non-experts, without removing the technical details. (May 2021) (Learn how and when to remove this template message)

Indistinguishability obfuscation (IO) is a cryptographic primitive that provides a formal notion of program obfuscation. Informally, obfuscation hides the implementation of a program while still allowing users to run it.^[1] Formally, IO satisfies the property that any two obfuscations of two circuits of the same size which implement the same function are computationally indistinguishable.^[2]

History[]

The origin of this idea came from Amit Sahai in 1996 from the notion of a zero-knowledge proof.^[3]

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.^{[3][4][5][2][verification needed]}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.^[3][6] (However, for inefficient obfuscators, no best-possible obfuscator exists unless the polynomial hierarchy collapses to the second level.^[6])

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.^[4] If P = NP holds, then an indistinguishability obfuscator exists, even though no other kind of cryptography would also exist.^[2]

A candidate construction of IO with provable security under concrete hardness assumptions relating to multilinear maps was published in 2013,^[2][7][8] but this assumption was later invalidated.^[7][8] (Previously, Garg, Gentry, and Halevi (2012) had constructed a candidate version of a multilinear map based on heuristic assumptions.^[9])

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.^[8] 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,^[8][10] as well as the existence of a super-linear stretch pseudorandom generator in the function class NC⁰.^[10] (The existence of pseudorandom generators in NC⁰ (even with sub-linear stretch) was a long-standing open problem until 2006.^[11]) 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).^{[8][speculation?]}

Practicability?[]

There have been attempts to implement and benchmark IO candidates.^[2] For example, as of 2017, an obfuscation of the function ${\displaystyle 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.^[2] Additionally, an obfuscation of the Advanced Encryption Standard hash function at a security level of 128 bits would measure 18 PB and have an evaluation time of about 272 years.^[2] An open-source software implementation of an IO candidate was created in 2015.^[12]

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^[1][8] 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:

• Indistinguishability obfuscation for programs in the RAM model^[10] and for Turing machines^[13][14]
• Public-key cryptography (and an IND-CCA-secure version)^[15]
• Short digital signatures^[15]
• IND-CCA-secure key encapsulation schemes^[15]
• Perfectly zero-knowledge non-interactive zero-knowledge proofs and succinct non-interactive arguments^[15]
• Constant-round concurrent zero-knowledge protocols^[10]
• Multilinear maps with bounded polynomial degrees^[10]
• Injective trapdoor functions^[15]
• Fully homomorphic encryption^[10]
• ^[10][2]
• Functional encryption^[2]
• Secret sharing for any monotone NP language^[10]
• Semi-honest oblivious transfer^[15]
• Deniable encryption (both sender-deniable and fully-deniable)^[15][10][2]
• Multiparty, non-interactive key exchange^[10]
• Adaptively secure succinct garbled RAM^[10]
• Correlation intractable functions^[10]
• Attribute-based encryption^[10]
• Oblivious transfer^[2]
• Traitor tracing^[2]
• Graded encoding schemes^[2]

(Additionally, we can also prove that problems in the PPAD complexity class are hard.^[10]) 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, unless with an exponential loss of security.^[16]

See also[]

• Black-box obfuscation, a stronger form of obfuscation proven to be impossible

References[]