Indistinguishability obfuscation
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] A candidate construction of IO with provable security under concrete hardness assumptions relating to multilinear maps was published in 2013, but this assumption was later invalidated.[2][3] 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.[3] However, none have achieved widespread acceptance to date, and 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 any pseudorandom generators in NC0 (even with sub-linear stretch) was a long-standing open problem until 2006,[4] and the question of the existence of one with super-linear stretch is still open.
See also
- Black-box obfuscation, a stronger form of obfuscation proven to be impossible
References
- 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.
- Applebaum, B; Ishai, Y; Kushilevitz, E (2006). "Cryptography in NC0" (PDF). SIAM Journal on Computing. 36 (4): 845–888.