This article may be too technical for most readers to understand.(May 2021)
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.
Work has continued attempting to establish preconditions from more standard assumptions, notably the 2020 work of Jain, Lin, and Sahai based on the XDH, LWE, and LPN assumptions. The Jain, Lin, and Sahai proposal also requires the existence of a super-linear stretch pseudorandom generator in the function class NC0. The existence of pseudorandom generators in NC0 (even with sub-linear stretch) was a long-standing open problem until 2006.
Indistinguishability obfuscators, if they exist, could be used for an enormous range of cryptographic applications. Concretely, an indistinguishability obfuscator could be used to construct the following kinds of cryptography:
- Public-key cryptography (and an IND-CCA-secure version)
- Short digital signatures
- IND-CCA-secure key encapsulation schemes
- Perfectly zero-knowledge non-interactive zero-knowledge proofs and succinct non-interactive arguments
- Constant-round concurrent zero-knowledge protocols
- Multilinear maps with bounded polynomial degrees
- Injective trapdoor functions
- Fully homomorphic encryption
- Witness encryption
- Secret sharing for any monotone NP language
- Semi-honest oblivious transfer
- Deniable encryption (both sender-deniable and fully-deniable)
- Multiparty, non-interactive key exchange
- Adaptively secure succinct garbled RAM
- Indistinguishability obfuscation for programs in the RAM model
- Correlation intractable functions
- Attribute-based encryption
- PPAD hardness.
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.
- Black-box obfuscation, a stronger form of obfuscation proven to be impossible
- Klarreich, Erica (2014-02-03). "Cryptography Breakthrough Could Make Software Unhackable". Quanta Magazine.
- Sanjam Garg; Craig Gentry; Shai Halevi; Mariana Raykova; Amit Sahai; Brent Waters (2013). "Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits". Focs 2013. IEEE: 40–49. CiteSeerX 10.1.1.672.1968. doi:10.1109/FOCS.2013.13. ISBN 978-0-7695-5135-7.
- Klarreich, Erica (2020-10-10). "Computer Scientists Achieve 'Crown Jewel' of Cryptography". Quanta Magazine.
- Jain, Aayush; Lin, Huijia; Sahai, Amit (2020). "Indistinguishability Obfuscation from Well-Founded Assumptions". arXiv:2008.09317. Cite journal requires
- Applebaum, B; Ishai, Y; Kushilevitz, E (2006). "Cryptography in NC0" (PDF). SIAM Journal on Computing. 36 (4): 845–888. doi:10.1137/S0097539705446950.
- Sahai, Amit; Waters, Brent (2013). "How to Use Indistinguishability Obfuscation: Deniable Encryption, and More". Cite journal requires
- Asharov, Gilad; Segev, Gil (2015). "Limits on the Power of Indistinguishability Obfuscation and Functional Encryption". Cite journal requires