indistinguishability obfuscation

In cryptography, indistinguishability obfuscation (abbreviated IO or iO) is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot be distinguished from each other. Informally, such obfuscation hides the implementation of a program while still allowing users to run it.{{cite news |last=Klarreich |first=Erica |author-link=Erica Klarreich |date=2014-02-03 |title=Cryptography Breakthrough Could Make Software Unhackable |url=https://www.wired.com/2014/02/cryptography-breakthrough/ |newspaper=Quanta Magazine |access-date=2019-02-15 |archive-date=2022-04-14 |archive-url=https://web.archive.org/web/20220414061648/https://www.wired.com/2014/02/cryptography-breakthrough/ |url-status=live }} Formally, iO satisfies the property that obfuscations of two circuits of the same size which implement the same function are computationally indistinguishable.

Indistinguishability obfuscation has several interesting theoretical properties. Firstly, iO is the "best-possible" obfuscation (in the sense that any secret about a program that can be hidden by any obfuscator at all can also be hidden by iO). Secondly, iO can be used to construct nearly the entire gamut of cryptographic primitives, including both mundane ones such as public-key cryptography and more exotic ones such as deniable encryption and functional encryption (which are types of cryptography that no-one previously knew how to construct), but with the notable exception of collision-resistant hash function families. For this reason, it has been referred to as "crypto-complete". Lastly, unlike many other kinds of cryptography, indistinguishability obfuscation continues to exist even if P=NP (though it would have to be constructed differently in this case), though this does not necessarily imply that iO exists unconditionally.

Though the idea of cryptographic software obfuscation has been around since 1996, indistinguishability obfuscation was first proposed by Barak et al. (2001), who proved that iO exists if P=NP is the case. For the P≠NP case (which is harder, but also more plausible), progress was slower: Garg et al. (2013) proposed a construction of iO based on a computational hardness assumption relating to multilinear maps, but this assumption was later disproven. A construction based on "well-founded assumptions" (hardness assumptions that have been well-studied by cryptographers, and thus widely assumed secure) had to wait until Jain, Lin, and Sahai (2020). (Even so, one of these assumptions used in the 2020 proposal is not secure against quantum computers.)

Currently known indistinguishability obfuscation candidates are very far from being practical. As measured by a 2017 paper,{{Update inline|date=January 2022|reason=Has someone checked this for Jain et al. (2020)'s proposal yet, or any of the other more recent ones? (Though, judging by the sheer number of reductions that the proposal has to go through, I would guess that it wouldn't fare much better.) ~Duckmather}} even obfuscating the toy function which outputs the logical conjunction of its thirty-two Boolean data type inputs produces a program nearly a dozen gigabytes large.

Formal definition

Let $\mathcal{iO}$ be some uniform probabilistic polynomial-time algorithm. Then $\mathcal{iO}$ is called an indistinguishability obfuscator if and only if it satisfies both of the following two statements:

Completeness or Functionality: For any Boolean circuit C of input length n and input $x\in\{0, 1\}^n$ , we have $\Pr[C'(x) = C(x): C' \leftarrow\mathcal{iO}(C) ] = 1.$
Indistinguishability: For every pair of circuits $C_0, C_1$ of the same size k that implement the same functionality, the distributions $\{\mathcal{iO}(C_0)\}$ and $\{\mathcal{iO}(C_1)\}$ are computationally indistinguishable. In other words, for any probabilistic polynomial-time adversary A, there is a negligible function $\varepsilon(k)$ (i.e., a function that eventually grows slower than $1/p(k)$ for any polynomial p) such that, for every pair of circuits $C_0, C_1$ of the same size k that implement the same functionality, we have $|\Pr[A(\mathcal{iO}(C_0))=1] - \Pr[A(\mathcal{iO}(C_1))=1]|\leq\varepsilon(k).$

History

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.{{Cite web|last=Klarreich|first=Erica|date=2014-01-30|title=Perfecting the Art of Sensible Nonsense|url=https://www.quantamagazine.org/in-cryptography-advances-in-program-obfuscation-20140130/|access-date=2021-08-22|website=Quanta Magazine|language=en|archive-date=2021-08-06|archive-url=https://web.archive.org/web/20210806002418/https://www.quantamagazine.org/in-cryptography-advances-in-program-obfuscation-20140130/|url-status=live}}{{Cite journal|last1=Barak|first1=Boaz|last2=Goldreich|first2=Oded|last3=Impagliazzo|first3=Russell|last4=Rudich|first4=Steven|last5=Sahai|first5=Amit|last6=Vadhan|first6=Salil|last7=Yang|first7=Ke|date=2012-05-03|title=On the (im)possibility of obfuscating programs|url=https://dash.harvard.edu/bitstream/handle/1/12644697/9034637.pdf|journal=Journal of the ACM|volume=59|issue=2|pages=6:1–6:48|doi=10.1145/2160158.2160159|s2cid=2409597|issn=0004-5411|access-date=2024-06-30|archive-date=2023-02-25|archive-url=https://web.archive.org/web/20230225203000/https://dash.harvard.edu/bitstream/handle/1/12644697/9034637.pdf|url-status=live}}{{Cite web|last=Pellet--Mary|first=Alice|date=26 May 2020|title=Co6GC: Program Obfuscation {{!}} COSIC|url=https://www.esat.kuleuven.be/cosic/blog/program-obfuscation/|url-status=live|archive-url=https://web.archive.org/web/20201111005432/https://www.esat.kuleuven.be/cosic/blog/program-obfuscation/|archive-date=11 November 2020|access-date=22 August 2021|website=www.esat.kuleuven.be}} 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.{{Cite book|last1=Goldwasser|first1=Shafi|author-link=Shafi Goldwasser|last2=Rothblum|first2=Guy N.|title=Theory of Cryptography|chapter=On Best-Possible Obfuscation|year=2007|editor-last=Vadhan|editor-first=Salil P.|chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-70936-7_11|series=Lecture Notes in Computer Science|volume=4392|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=194–213|doi=10.1007/978-3-540-70936-7_11|isbn=978-3-540-70936-7|hdl=1721.1/129413|hdl-access=free|access-date=2021-08-22|archive-date=2022-01-19|archive-url=https://web.archive.org/web/20220119065725/https://link.springer.com/chapter/10.1007%2F978-3-540-70936-7_11|url-status=live}} (However, for inefficient obfuscators, no best-possible obfuscator exists unless the polynomial hierarchy collapses to the second level.)

An open-source software implementation of an iO candidate was created in 2015.{{Cite book |last1=Banescu |first1=Sebastian |last2=Ochoa |first2=Martín |last3=Kunze |first3=Nils |last4=Pretschner |first4=Alexander |title=Engineering Secure Software and Systems |chapter=Idea: Benchmarking Indistinguishability Obfuscation – A Candidate Implementation |year=2015 |editor-last=Piessens |editor-first=Frank |editor2-last=Caballero |editor2-first=Juan |editor3-last=Bielova |editor3-first=Nataliia |chapter-url=https://www.cqse.eu/fileadmin/content/news/publications/2015-idea-benchmarking-indistinguishability-obfuscation-a-candidate-implementation.pdf |series=Lecture Notes in Computer Science |language=en |location=Cham |publisher=Springer International Publishing |volume=8978 |pages=149–156 |doi=10.1007/978-3-319-15618-7_12 |isbn=978-3-319-15618-7 |access-date=2021-08-22 |archive-date=2021-08-22 |archive-url=https://web.archive.org/web/20210822025910/https://www.cqse.eu/fileadmin/content/news/publications/2015-idea-benchmarking-indistinguishability-obfuscation-a-candidate-implementation.pdf |url-status=live }}

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

A candidate construction of iO with provable security under concrete hardness assumptions relating to multilinear maps was published by Garg et al. (2013), but this assumption was later invalidated.{{Cite book |last1=Garg |first1=Sanjam |last2=Gentry |first2=Craig |last3=Halevi |first3=Shai |last4=Raykova |first4=Mariana |last5=Sahai |first5=Amit |last6=Waters |first6=Brent |chapter=Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits |date=2013 |title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |chapter-url=http://dx.doi.org/10.1109/focs.2013.13 |pages=40–49 |publisher=IEEE |doi=10.1109/focs.2013.13|isbn=978-0-7695-5135-7 }}{{cite news |last=Klarreich |first=Erica |author-link=Erica Klarreich |date=2020-10-10 |title=Computer Scientists Achieve 'Crown Jewel' of Cryptography |url=https://www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/ |newspaper=Quanta Magazine |access-date=2020-11-10 |archive-date=2022-05-07 |archive-url=https://web.archive.org/web/20220507013835/https://www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/ |url-status=live }} (Previously, Garg, Gentry, and Halevi (2012) had constructed a candidate version of a multilinear map based on heuristic assumptions.{{Cite web|last=Barak|first=Boaz|date=29 December 2020|title=New Developments in Indistinguishability Obfuscation (iO) {{!}} Simons Institute for the Theory of Computing|url=https://simons.berkeley.edu/news/new-developments-indistinguishability-obfuscation-io|access-date=22 August 2021|website=simons.berkeley.edu|language=en|archive-date=22 August 2021|archive-url=https://web.archive.org/web/20210822025918/https://simons.berkeley.edu/news/new-developments-indistinguishability-obfuscation-io|url-status=live}})

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. 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,{{Cite journal|last1=Jain|first1=Aayush|last2=Lin|first2=Huijia|author2-link=Huijia (Rachel) Lin|last3=Sahai|first3=Amit|year=2020|title=Indistinguishability Obfuscation from Well-Founded Assumptions|journal=Cryptology ePrint Archive|arxiv=2008.09317|url=https://eprint.iacr.org/2020/1003|access-date=2020-11-16|archive-date=2022-03-03|archive-url=https://web.archive.org/web/20220303200221/https://eprint.iacr.org/2020/1003|url-status=live}} as well as the existence of a super-linear stretch pseudorandom generator in the function class NC⁰. (The existence of pseudorandom generators in NC⁰ (even with sub-linear stretch) was a long-standing open problem until 2006.{{cite journal |last1=Applebaum |first1=B |last2=Ishai |first2=Y |last3=Kushilevitz |first3=E |title=Cryptography in NC0 |journal=SIAM Journal on Computing |year=2006 |volume=36 |issue=4 |pages=845–888 |doi=10.1137/S0097539705446950 |url=http://www.eng.tau.ac.il/%7Ebennyap/pubs/nc0-full.pdf |access-date=2020-11-11 |archive-date=2021-11-30 |archive-url=https://web.archive.org/web/20211130194319/http://www.eng.tau.ac.il/~bennyap/pubs/nc0-full.pdf |url-status=dead }}) 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).{{Speculation inline|date=August 2023}}

= Practicality =

There have been attempts to implement and benchmark iO candidates. In 2017, an obfuscation of the function $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. Additionally, an obfuscation of the Advanced Encryption Standard encryption circuit at a security level of 128 bits would measure 18 PB and have an evaluation time of about 272 years.

Existence

It is useful to divide the question of the existence of iO by using Russell Impagliazzo's "five worlds",{{cite book |last1=Impagliazzo |first1=Russell |title=Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference |chapter=A personal view of average-case complexity |date=19–22 June 1995 |pages=134–147 |doi=10.1109/SCT.1995.514853 |isbn=0-8186-7052-5 |s2cid=2154064 |chapter-url=https://ieeexplore.ieee.org/document/514853 |access-date=27 July 2022 |archive-date=27 July 2022 |archive-url=https://web.archive.org/web/20220727153101/https://ieeexplore.ieee.org/document/514853/ |url-status=live }} which are five different hypothetical situations about average-case complexity:{{Cite journal|last1=Moran|first1=Tal|last2=Rosen|first2=Alon|date=7 October 2013|title=There is no Indistinguishability Obfuscation in Pessiland|url=https://eprint.iacr.org/2013/643.pdf|journal=IACR Cryptology ePrint Archive|access-date=15 January 2022|archive-date=19 January 2022|archive-url=https://web.archive.org/web/20220119062601/https://eprint.iacr.org/2013/643.pdf|url-status=live}}

Algorithmica: In this case P = NP, but iO exists.
Heuristica: In this case NP problems are easy on average; iO does not exist.{{Dubious|date=January 2022|reason=}}
Pessiland: In this case, BPP ≠ NP, but one-way functions do not exist; as a result, iO does not exist.
Minicrypt: In this case, one-way functions exist, but secure public-key cryptography does not; iO does not exist (because explicit constructions of public-key cryptography from iO and one-way functions are known).
Cryptomania: In this case, secure public-key cryptography exists, but iO does not exist.
Obfustopia:{{Cite journal|last1=Bitansky|first1=Nir|last2=Nishimaki|first2=Ryo|last3=Passelègue|first3=Alain|last4=Wichs|first4=Daniel|date=30 August 2017|title=From Cryptomania to Obfustopia through Secret-Key Functional Encryption|url=https://eprint.iacr.org/2016/558.pdf|journal=IACR Cryptology ePrint Archive|access-date=15 January 2022|archive-date=20 January 2022|archive-url=https://web.archive.org/web/20220120203308/https://eprint.iacr.org/2016/558.pdf|url-status=live}}{{Cite book|last1=Garg|first1=Sanjam|last2=Pandey|first2=Omkant|last3=Srinivasan|first3=Akshayaram|last4=Zhandry|first4=Mark|title=Advances in Cryptology – EUROCRYPT 2017|chapter=Breaking the Sub-Exponential Barrier in Obfustopia|year=2017|editor-last=Coron|editor-first=Jean-Sébastien|editor2-last=Nielsen|editor2-first=Jesper Buus|chapter-url=https://link.springer.com/chapter/10.1007/978-3-319-56617-7_6|series=Lecture Notes in Computer Science|volume=10212|language=en|location=Cham|publisher=Springer International Publishing|pages=156–181|doi=10.1007/978-3-319-56617-7_6|isbn=978-3-319-56617-7|access-date=2022-01-15|archive-date=2022-01-15|archive-url=https://web.archive.org/web/20220115210326/https://link.springer.com/chapter/10.1007/978-3-319-56617-7_6|url-status=live}} In this case, iO is believed to exist.

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, the "crown jewel of cryptography", or "crypto-complete". Concretely, an indistinguishability obfuscator (with the additional assumption of the existence of one-way functions) could be used to construct the following kinds of cryptography:

Indistinguishability obfuscation for programs in the RAM model and for Turing machines{{Cite book|last1=Koppula|first1=Venkata|last2=Lewko|first2=Allison Bishop|last3=Waters|first3=Brent|title=Proceedings of the forty-seventh annual ACM symposium on Theory of Computing|chapter=Indistinguishability Obfuscation for Turing Machines with Unbounded Memory|date=2015-06-14|chapter-url=https://eprint.iacr.org/2014/925.pdf|series=STOC '15|location=Portland, Oregon, USA|publisher=Association for Computing Machinery|pages=419–428|doi=10.1145/2746539.2746614|isbn=978-1-4503-3536-2|s2cid=1368494|access-date=2021-09-11|archive-date=2021-09-11|archive-url=https://web.archive.org/web/20210911211015/https://eprint.iacr.org/2014/925.pdf|url-status=live}}{{Cite book|last1=Ananth|first1=Prabhanjan|last2=Jain|first2=Abhishek|last3=Sahai|first3=Amit|title=Advances in Cryptology – CRYPTO 2017|chapter=Indistinguishability Obfuscation for Turing Machines: Constant Overhead and Amortization|year=2017|editor-last=Katz|editor-first=Jonathan|editor2-last=Shacham|editor2-first=Hovav|chapter-url=https://eprint.iacr.org/2015/1023.pdf|series=Lecture Notes in Computer Science|volume=10402|language=en|location=Cham|publisher=Springer International Publishing|pages=252–279|doi=10.1007/978-3-319-63715-0_9|isbn=978-3-319-63715-0|access-date=2021-09-11|archive-date=2021-09-11|archive-url=https://web.archive.org/web/20210911211004/https://eprint.iacr.org/2015/1023.pdf|url-status=live}}
IND-CCA-secure public-key cryptography{{Cite journal|last1=Sahai|first1=Amit|last2=Waters|first2=Brent|year=2013|title=How to Use Indistinguishability Obfuscation: Deniable Encryption, and More|journal=Cryptology ePrint Archive|url=https://eprint.iacr.org/2013/454|access-date=2021-03-14|archive-date=2022-02-03|archive-url=https://web.archive.org/web/20220203232604/https://eprint.iacr.org/2013/454|url-status=live}}
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
Functional 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
Correlation intractable functions
Attribute-based encryption
Oblivious transfer
Traitor tracing
Graded encoding schemes

Additionally, if iO and one-way functions exist, then problems in the PPAD complexity class are provably hard.{{Cite book|last1=Bitansky|first1=Nir|last2=Paneth|first2=Omer|last3=Rosen|first3=Alon|title=2015 IEEE 56th Annual Symposium on Foundations of Computer Science|chapter=On the Cryptographic Hardness of Finding a Nash Equilibrium|date=October 2015|chapter-url=https://ieeexplore.ieee.org/document/7354468|pages=1480–1498|doi=10.1109/FOCS.2015.94|isbn=978-1-4673-8191-8|s2cid=217890992|access-date=2024-06-30|archive-date=2024-06-10|archive-url=https://web.archive.org/web/20240610203415/https://ieeexplore.ieee.org/document/7354468/|url-status=live}}

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, except with an exponential loss of security.{{Cite journal|last1=Asharov|first1=Gilad|last2=Segev|first2=Gil|year=2015|title=Limits on the Power of Indistinguishability Obfuscation and Functional Encryption|journal=Cryptology ePrint Archive|url=https://eprint.iacr.org/2015/341|access-date=2021-03-14|archive-date=2022-01-21|archive-url=https://web.archive.org/web/20220121020431/https://eprint.iacr.org/2015/341|url-status=live}}

References

Category:Cryptographic primitives

Category:Software obfuscation