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]
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:
- Public-key cryptography (and an IND-CCA-secure version)[6]
- Short digital signatures[6]
- IND-CCA-secure key encapsulation schemes[6]
- Perfectly zero-knowledge non-interactive zero-knowledge proofs and succinct non-interactive arguments[6]
- Constant-round concurrent zero-knowledge protocols[4]
- Multilinear maps with bounded polynomial degrees[4]
- Injective trapdoor functions[6]
- Fully homomorphic encryption[4]
- Witness encryption[4]
- Secret sharing for any monotone NP language[4]
- Semi-honest oblivious transfer[6]
- Deniable encryption (both sender-deniable and fully-deniable)[6][4]
- Multiparty, non-interactive key exchange[4]
- Adaptively secure succinct garbled RAM[4]
- Indistinguishability obfuscation for programs in the RAM model[4]
- Correlation intractable functions[4]
- Attribute-based encryption[4]
- PPAD hardness.[4]
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]
- Black-box obfuscation, a stronger form of obfuscation proven to be impossible
References[edit]
- ^ a b 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.
- ^ a b c Klarreich, Erica (2020-10-10). "Computer Scientists Achieve 'Crown Jewel' of Cryptography". Quanta Magazine.
- ^ 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) - ^ Applebaum, B; Ishai, Y; Kushilevitz, E (2006). "Cryptography in NC0" (PDF). SIAM Journal on Computing. 36 (4): 845–888.
- ^ 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) - ^ Asharov, Gilad; Segev, Gil (2015). "Limits on the Power of Indistinguishability Obfuscation and Functional Encryption". Cite journal requires
|journal=(help)
 | This cryptography-related article is a stub. You can help Wikipedia by expanding it. |