Indistinguishability obfuscation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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]

Candidate constructions[edit]

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][4] The Jain, Lin, and Sahai proposal also requires the existence of a super-linear stretch pseudorandom generator in the function class NC0.[4] The existence of pseudorandom generators in NC0 (even with sub-linear stretch) was a long-standing open problem until 2006.[5]

Potential applications[edit]

Indistinguishability obfuscators, if they exist, could be used for an enormous range of cryptographic applications.[1][3] Concretely, an indistinguishability obfuscator could be used to construct the following kinds of cryptography:

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.[7]

See also[edit]

References[edit]

  1. ^ a b Klarreich, Erica (2014-02-03). "Cryptography Breakthrough Could Make Software Unhackable". Quanta Magazine.
  2. ^ 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.
  3. ^ a b c Klarreich, Erica (2020-10-10). "Computer Scientists Achieve 'Crown Jewel' of Cryptography". Quanta Magazine.
  4. ^ a b c d e f g h i j k l m n Jain, Aayush; Lin, Huijia; Sahai, Amit (2020). "Indistinguishability Obfuscation from Well-Founded Assumptions". Cite journal requires |journal= (help)
  5. ^ Applebaum, B; Ishai, Y; Kushilevitz, E (2006). "Cryptography in NC0" (PDF). SIAM Journal on Computing. 36 (4): 845–888.
  6. ^ a b c d e f g Sahai, Amit; Waters, Brent (2013). "How to Use Indistinguishability Obfuscation: Deniable Encryption, and More". Cite journal requires |journal= (help)
  7. ^ Asharov, Gilad; Segev, Gil (2015). "Limits on the Power of Indistinguishability Obfuscation and Functional Encryption". Cite journal requires |journal= (help)