Indistinguishability obfuscation

Last updated October 11, 2024

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.^[1] Formally, iO satisfies the property that obfuscations of two circuits of the same size which implement the same function are computationally indistinguishable.^[2]

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^[3]), 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^[2]), progress was slower: Garg et al. (2013)^[4] 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,^{[ needs update ]} 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:^[5]^[6]^[7]

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.^[8]^[7]^[2] 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.^[8]^[9] (However, for inefficient obfuscators, no best-possible obfuscator exists unless the polynomial hierarchy collapses to the second level.^[9])

An open-source software implementation of an iO candidate was created in 2015.^[10]

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

A candidate construction of iO with provable security under concrete hardness assumptions relating to multilinear maps was published by Garg et al. (2013),^[2]^[11]^[3] but this assumption was later invalidated.^[11]^[3] (Previously, Garg, Gentry, and Halevi (2012) had constructed a candidate version of a multilinear map based on heuristic assumptions.^[4])

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.^[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,^[3]^[5] as well as the existence of a super-linear stretch pseudorandom generator in the function class NC⁰.^[5] (The existence of pseudorandom generators in NC⁰ (even with sub-linear stretch) was a long-standing open problem until 2006.^[12]) 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).^[3]^{[ speculation? ]}

Practicality

There have been attempts to implement and benchmark iO candidates.^[2] 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.^[2] 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.^[2]

Existence

It is useful to divide the question of the existence of iO by using Russell Impagliazzo's "five worlds",^[13] which are five different hypothetical situations about average-case complexity:^[6]

Algorithmica: In this case P = NP, but iO exists.
Heuristica: In this case NP problems are easy on average; iO does not exist.^{[ dubious – discuss ]}
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:^[14]^[15] 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,^[1]^[3] the "crown jewel of cryptography",^[3] or "crypto-complete".^[2] Concretely, an indistinguishability obfuscator (with the additional assumption of the existence of one-way functions ^[2]) could be used to construct the following kinds of cryptography:

Indistinguishability obfuscation for programs in the RAM model^[5] and for Turing machines ^[16]^[17]
IND-CCA-secure public-key cryptography ^[18]
Short digital signatures ^[18]
IND-CCA-secure key encapsulation schemes^[18]
Perfectly zero-knowledge non-interactive zero-knowledge proofs and succinct non-interactive arguments^[18]
Constant-round concurrent zero-knowledge protocols^[5]
Multilinear maps with bounded polynomial degrees^[5]
Injective trapdoor functions ^[18]
Fully homomorphic encryption ^[5]
Witness encryption ^[5]^[2]
Functional encryption ^[2]
Secret sharing for any monotone NP language^[5]
Semi-honest oblivious transfer ^[18]
Deniable encryption (both sender-deniable and fully-deniable)^[18]^[5]^[2]
Multiparty, non-interactive key exchange ^[5]
Adaptively secure succinct garbled RAM^[5]
Correlation intractable functions^[5]
Attribute-based encryption^[5]
Oblivious transfer^[2]
Traitor tracing^[2]
Graded encoding schemes^[2]

Additionally, if iO and one-way functions exist, then problems in the PPAD complexity class are provably hard.^[5]^[19]

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

Related Research Articles

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.

Identity-based encryption (IBE), is an important primitive of identity-based cryptography. As such it is a type of public-key encryption in which the public key of a user is some unique information about the identity of the user. This means that a sender who has access to the public parameters of the system can encrypt a message using e.g. the text-value of the receiver's name or email address as a key. The receiver obtains its decryption key from a central authority, which needs to be trusted as it generates secret keys for every user.

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

In cryptography, a zero-knowledge proof is a protocol in which one party can convince another party that some given statement is true, without conveying to the verifier any information beyond the mere fact of that statement's truth. The intuition underlying zero-knowledge proofs is that it is trivial to prove possession of the relevant information simply by revealing it; the hard part is to prove this possession without revealing this information.

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

In theoretical computer science and cryptography, a pseudorandom generator (PRG) for a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class can distinguish between the output of the generator and the uniform distribution. The random seed itself is typically a short binary string drawn from the uniform distribution.

Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt. The property of indistinguishability under chosen plaintext attack is considered a basic requirement for most provably secure public key cryptosystems, though some schemes also provide indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack. Indistinguishability under chosen plaintext attack is equivalent to the property of semantic security, and many cryptographic proofs use these definitions interchangeably.

In cryptography, a verifiable random function (VRF) is a public-key pseudorandom function that provides proofs that its outputs were calculated correctly. The owner of the secret key can compute the function value as well as an associated proof for any input value. Everyone else, using the proof and the associated public key, can check that this value was indeed calculated correctly, yet this information cannot be used to find the secret key.

In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle. Pseudorandom functions are vital tools in the construction of cryptographic primitives, especially secure encryption schemes.

Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it. The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that produced had the operations been performed on the unencrypted data. Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and outsourced to commercial cloud environments for processing, all while encrypted.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

Secure two-party computation (2PC) a.k.a. Secure function evaluation is sub-problem of secure multi-party computation (MPC) that has received special attention by researchers because of its close relation to many cryptographic tasks. The goal of 2PC is to create a generic protocol that allows two parties to jointly compute an arbitrary function on their inputs without sharing the value of their inputs with the opposing party. One of the most well known examples of 2PC is Yao's Millionaires' problem, in which two parties, Alice and Bob, are millionaires who wish to determine who is wealthier without revealing their wealth. Formally, Alice has wealth $, Bob has wealth, and they wish to compute without revealing the values or .$

The framework of universal composability (UC) is a general-purpose model for the analysis of cryptographic protocols. It guarantees very strong security properties. Protocols remain secure even if arbitrarily composed with other instances of the same or other protocols. Security is defined in the sense of protocol emulation. Intuitively, a protocol is said to emulate another one, if no environment (observer) can distinguish the executions. Literally, the protocol may simulate the other protocol. The notion of security is derived by implication. Assume a protocol $is secure per definition. If another protocol emulates protocol such that no environment tells apart the emulation from the execution of the protocol, then the emulated protocol is as secure as protocol .$

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

Hardware obfuscation is a technique by which the description or the structure of electronic hardware is modified to intentionally conceal its functionality, which makes it significantly more difficult to reverse-engineer. In other words, hardware obfuscation modifies the design in such a away that the resulting architecture becomes un-obvious to an adversary. Hardware Obfuscation can be of two types depending on the hardware platform targeted: (a) DSP Core Hardware Obfuscation - this type of obfuscation performs certain high level transformation on the data flow graph representation of DSP core to convert it into an unknown form that reflects an un-obvious architecture at RTL or gate level. This type of obfuscation is also called 'Structural Obfuscation'. Another type of DSP Core Obfuscation method is called 'Functional Obfuscation' - It uses a combination of AES and IP core locking blocks (ILBs) to lock the functionality of the DSP core using key-bits. Without application of correct key sequence, the DSP core produces either wrong output or no output at all (b) Combinational/Sequential Hardware Obfuscation - this type of obfuscation performs changes to the gate level structure of the circuit itself.

<span class="mw-page-title-main">Functional encryption</span>

Functional encryption (FE) is a generalization of public-key encryption in which possessing a secret key allows one to learn a function of what the ciphertext is encrypting.

Amit Sahai is an Indian-American computer scientist. He is a professor of computer science at UCLA and the director of the Center for Encrypted Functionalities.

Shai Halevi is a computer scientist who works on cryptography research at Amazon Web Services.

A cryptographic $-multilinear map$ is a kind of multilinear map, that is, a function $such that for any integers and elements,, and which in addition is efficiently computable and satisfies some security properties. It has several applications on cryptography, as key exchange protocols, identity-based encryption, and broadcast encryption. There exist constructions of cryptographic 2-multilinear maps, known as bilinear maps, however, the problem of constructing such multilinear maps for seems much more difficult and the security of the proposed candidates is still unclear.$

In cryptography, black-box obfuscation was a proposed cryptographic primitive which would allow a computer program to be obfuscated in a way such that it was impossible to determine anything about it except its input and output behavior. Black-box obfuscation has been proven to be impossible, even in principle.

References

1 2 Klarreich, Erica (2014-02-03). "Cryptography Breakthrough Could Make Software Unhackable". Quanta Magazine. Archived from the original on 2022-04-14. Retrieved 2019-02-15.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Pellet--Mary, Alice (26 May 2020). "Co6GC: Program Obfuscation | COSIC". www.esat.kuleuven.be. Archived from the original on 11 November 2020. Retrieved 22 August 2021.
1 2 3 4 5 6 7 8 Klarreich, Erica (2020-10-10). "Computer Scientists Achieve 'Crown Jewel' of Cryptography". Quanta Magazine. Archived from the original on 2022-05-07. Retrieved 2020-11-10.
1 2 Barak, Boaz (29 December 2020). "New Developments in Indistinguishability Obfuscation (iO) | Simons Institute for the Theory of Computing". simons.berkeley.edu. Archived from the original on 22 August 2021. Retrieved 22 August 2021.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Jain, Aayush; Lin, Huijia; Sahai, Amit (2020). "Indistinguishability Obfuscation from Well-Founded Assumptions". Cryptology ePrint Archive. arXiv: 2008.09317 . Archived from the original on 2022-03-03. Retrieved 2020-11-16.
1 2 Moran, Tal; Rosen, Alon (7 October 2013). "There is no Indistinguishability Obfuscation in Pessiland" (PDF). IACR Cryptology ePrint Archive. Archived (PDF) from the original on 19 January 2022. Retrieved 15 January 2022.
1 2 3 Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke (2012-05-03). "On the (im)possibility of obfuscating programs" (PDF). Journal of the ACM. 59 (2): 6:1–6:48. doi:10.1145/2160158.2160159. ISSN 0004-5411. S2CID 2409597. Archived (PDF) from the original on 2023-02-25. Retrieved 2024-06-30.
1 2 Klarreich, Erica (2014-01-30). "Perfecting the Art of Sensible Nonsense". Quanta Magazine. Archived from the original on 2021-08-06. Retrieved 2021-08-22.
1 2 Goldwasser, Shafi; Rothblum, Guy N. (2007). "On Best-Possible Obfuscation". In Vadhan, Salil P. (ed.). Theory of Cryptography. Lecture Notes in Computer Science. Vol. 4392. Berlin, Heidelberg: Springer. pp. 194–213. doi:10.1007/978-3-540-70936-7_11. hdl: 1721.1/129413 . ISBN 978-3-540-70936-7. Archived from the original on 2022-01-19. Retrieved 2021-08-22.
↑ Banescu, Sebastian; Ochoa, Martín; Kunze, Nils; Pretschner, Alexander (2015). "Idea: Benchmarking Indistinguishability Obfuscation – A Candidate Implementation" (PDF). In Piessens, Frank; Caballero, Juan; Bielova, Nataliia (eds.). Engineering Secure Software and Systems. Lecture Notes in Computer Science. Vol. 8978. Cham: Springer International Publishing. pp. 149–156. doi:10.1007/978-3-319-15618-7_12. ISBN 978-3-319-15618-7. Archived (PDF) from the original on 2021-08-22. Retrieved 2021-08-22.
1 2 Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2013). "Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE. pp. 40–49. doi:10.1109/focs.2013.13. ISBN 978-0-7695-5135-7.
↑ Applebaum, B; Ishai, Y; Kushilevitz, E (2006). "Cryptography in NC0" (PDF). SIAM Journal on Computing. 36 (4): 845–888. doi:10.1137/S0097539705446950. Archived from the original (PDF) on 2021-11-30. Retrieved 2020-11-11.
↑ Impagliazzo, Russell (19–22 June 1995). "A personal view of average-case complexity". Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference. pp. 134–147. doi:10.1109/SCT.1995.514853. ISBN 0-8186-7052-5. S2CID 2154064. Archived from the original on 27 July 2022. Retrieved 27 July 2022.
↑ Bitansky, Nir; Nishimaki, Ryo; Passelègue, Alain; Wichs, Daniel (30 August 2017). "From Cryptomania to Obfustopia through Secret-Key Functional Encryption" (PDF). IACR Cryptology ePrint Archive. Archived (PDF) from the original on 20 January 2022. Retrieved 15 January 2022.
↑ Garg, Sanjam; Pandey, Omkant; Srinivasan, Akshayaram; Zhandry, Mark (2017). "Breaking the Sub-Exponential Barrier in Obfustopia". In Coron, Jean-Sébastien; Nielsen, Jesper Buus (eds.). Advances in Cryptology – EUROCRYPT 2017. Lecture Notes in Computer Science. Vol. 10212. Cham: Springer International Publishing. pp. 156–181. doi:10.1007/978-3-319-56617-7_6. ISBN 978-3-319-56617-7. Archived from the original on 2022-01-15. Retrieved 2022-01-15.
↑ Koppula, Venkata; Lewko, Allison Bishop; Waters, Brent (2015-06-14). "Indistinguishability Obfuscation for Turing Machines with Unbounded Memory" (PDF). Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. STOC '15. Portland, Oregon, USA: Association for Computing Machinery. pp. 419–428. doi:10.1145/2746539.2746614. ISBN 978-1-4503-3536-2. S2CID 1368494. Archived (PDF) from the original on 2021-09-11. Retrieved 2021-09-11.
↑ Ananth, Prabhanjan; Jain, Abhishek; Sahai, Amit (2017). "Indistinguishability Obfuscation for Turing Machines: Constant Overhead and Amortization" (PDF). In Katz, Jonathan; Shacham, Hovav (eds.). Advances in Cryptology – CRYPTO 2017. Lecture Notes in Computer Science. Vol. 10402. Cham: Springer International Publishing. pp. 252–279. doi:10.1007/978-3-319-63715-0_9. ISBN 978-3-319-63715-0. Archived (PDF) from the original on 2021-09-11. Retrieved 2021-09-11.
1 2 3 4 5 6 7 Sahai, Amit; Waters, Brent (2013). "How to Use Indistinguishability Obfuscation: Deniable Encryption, and More". Cryptology ePrint Archive. Archived from the original on 2022-02-03. Retrieved 2021-03-14.
↑ Bitansky, Nir; Paneth, Omer; Rosen, Alon (October 2015). "On the Cryptographic Hardness of Finding a Nash Equilibrium". 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. pp. 1480–1498. doi:10.1109/FOCS.2015.94. ISBN 978-1-4673-8191-8. S2CID 217890992. Archived from the original on 2024-06-10. Retrieved 2024-06-30.
↑ Asharov, Gilad; Segev, Gil (2015). "Limits on the Power of Indistinguishability Obfuscation and Functional Encryption". Cryptology ePrint Archive. Archived from the original on 2022-01-21. Retrieved 2021-03-14.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Klarreich2014-1] 1 2 Klarreich, Erica (2014-02-03). "Cryptography Breakthrough Could Make Software Unhackable". Quanta Magazine. Archived from the original on 2022-04-14. Retrieved 2019-02-15.

[:4-2] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Pellet--Mary, Alice (26 May 2020). "Co6GC: Program Obfuscation | COSIC". www.esat.kuleuven.be. Archived from the original on 11 November 2020. Retrieved 22 August 2021.

[Klareich2020-3] 1 2 3 4 5 6 7 8 Klarreich, Erica (2020-10-10). "Computer Scientists Achieve 'Crown Jewel' of Cryptography". Quanta Magazine. Archived from the original on 2022-05-07. Retrieved 2020-11-10.

[:6-4] 1 2 Barak, Boaz (29 December 2020). "New Developments in Indistinguishability Obfuscation (iO) | Simons Institute for the Theory of Computing". simons.berkeley.edu. Archived from the original on 22 August 2021. Retrieved 22 August 2021.

[:0-5] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Jain, Aayush; Lin, Huijia; Sahai, Amit (2020). "Indistinguishability Obfuscation from Well-Founded Assumptions". Cryptology ePrint Archive. arXiv: 2008.09317 . Archived from the original on 2022-03-03. Retrieved 2020-11-16.

[:7-6] 1 2 Moran, Tal; Rosen, Alon (7 October 2013). "There is no Indistinguishability Obfuscation in Pessiland" (PDF). IACR Cryptology ePrint Archive. Archived (PDF) from the original on 19 January 2022. Retrieved 15 January 2022.

[:8-7] 1 2 3 Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke (2012-05-03). "On the (im)possibility of obfuscating programs" (PDF). Journal of the ACM. 59 (2): 6:1–6:48. doi:10.1145/2160158.2160159. ISSN 0004-5411. S2CID 2409597. Archived (PDF) from the original on 2023-02-25. Retrieved 2024-06-30.

[:2-8] 1 2 Klarreich, Erica (2014-01-30). "Perfecting the Art of Sensible Nonsense". Quanta Magazine. Archived from the original on 2021-08-06. Retrieved 2021-08-22.

[:5-9] 1 2 Goldwasser, Shafi; Rothblum, Guy N. (2007). "On Best-Possible Obfuscation". In Vadhan, Salil P. (ed.). Theory of Cryptography. Lecture Notes in Computer Science. Vol. 4392. Berlin, Heidelberg: Springer. pp. 194–213. doi:10.1007/978-3-540-70936-7_11. hdl: 1721.1/129413 . ISBN 978-3-540-70936-7. Archived from the original on 2022-01-19. Retrieved 2021-08-22.

[10] Banescu, Sebastian; Ochoa, Martín; Kunze, Nils; Pretschner, Alexander (2015). "Idea: Benchmarking Indistinguishability Obfuscation – A Candidate Implementation" (PDF). In Piessens, Frank; Caballero, Juan; Bielova, Nataliia (eds.). Engineering Secure Software and Systems. Lecture Notes in Computer Science. Vol. 8978. Cham: Springer International Publishing. pp. 149–156. doi:10.1007/978-3-319-15618-7_12. ISBN 978-3-319-15618-7. Archived (PDF) from the original on 2021-08-22. Retrieved 2021-08-22.

[GGHRSW-11] 1 2 Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2013). "Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE. pp. 40–49. doi:10.1109/focs.2013.13. ISBN 978-0-7695-5135-7.

[12] Applebaum, B; Ishai, Y; Kushilevitz, E (2006). "Cryptography in NC0" (PDF). SIAM Journal on Computing. 36 (4): 845–888. doi:10.1137/S0097539705446950. Archived from the original (PDF) on 2021-11-30. Retrieved 2020-11-11.

[13] Impagliazzo, Russell (19–22 June 1995). "A personal view of average-case complexity". Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference. pp. 134–147. doi:10.1109/SCT.1995.514853. ISBN 0-8186-7052-5. S2CID 2154064. Archived from the original on 27 July 2022. Retrieved 27 July 2022.

[14] Bitansky, Nir; Nishimaki, Ryo; Passelègue, Alain; Wichs, Daniel (30 August 2017). "From Cryptomania to Obfustopia through Secret-Key Functional Encryption" (PDF). IACR Cryptology ePrint Archive. Archived (PDF) from the original on 20 January 2022. Retrieved 15 January 2022.

[15] Garg, Sanjam; Pandey, Omkant; Srinivasan, Akshayaram; Zhandry, Mark (2017). "Breaking the Sub-Exponential Barrier in Obfustopia". In Coron, Jean-Sébastien; Nielsen, Jesper Buus (eds.). Advances in Cryptology – EUROCRYPT 2017. Lecture Notes in Computer Science. Vol. 10212. Cham: Springer International Publishing. pp. 156–181. doi:10.1007/978-3-319-56617-7_6. ISBN 978-3-319-56617-7. Archived from the original on 2022-01-15. Retrieved 2022-01-15.

[16] Koppula, Venkata; Lewko, Allison Bishop; Waters, Brent (2015-06-14). "Indistinguishability Obfuscation for Turing Machines with Unbounded Memory" (PDF). Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. STOC '15. Portland, Oregon, USA: Association for Computing Machinery. pp. 419–428. doi:10.1145/2746539.2746614. ISBN 978-1-4503-3536-2. S2CID 1368494. Archived (PDF) from the original on 2021-09-11. Retrieved 2021-09-11.

[17] Ananth, Prabhanjan; Jain, Abhishek; Sahai, Amit (2017). "Indistinguishability Obfuscation for Turing Machines: Constant Overhead and Amortization" (PDF). In Katz, Jonathan; Shacham, Hovav (eds.). Advances in Cryptology – CRYPTO 2017. Lecture Notes in Computer Science. Vol. 10402. Cham: Springer International Publishing. pp. 252–279. doi:10.1007/978-3-319-63715-0_9. ISBN 978-3-319-63715-0. Archived (PDF) from the original on 2021-09-11. Retrieved 2021-09-11.

[:1-18] 1 2 3 4 5 6 7 Sahai, Amit; Waters, Brent (2013). "How to Use Indistinguishability Obfuscation: Deniable Encryption, and More". Cryptology ePrint Archive. Archived from the original on 2022-02-03. Retrieved 2021-03-14.

[19] Bitansky, Nir; Paneth, Omer; Rosen, Alon (October 2015). "On the Cryptographic Hardness of Finding a Nash Equilibrium". 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. pp. 1480–1498. doi:10.1109/FOCS.2015.94. ISBN 978-1-4673-8191-8. S2CID 217890992. Archived from the original on 2024-06-10. Retrieved 2024-06-30.

[20] Asharov, Gilad; Segev, Gil (2015). "Limits on the Power of Indistinguishability Obfuscation and Functional Encryption". Cryptology ePrint Archive. Archived from the original on 2022-01-21. Retrieved 2021-03-14.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]