Indistinguishability obfuscation

Last updated

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]

Contents

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 be some uniform probabilistic polynomial-time algorithm. Then is called an indistinguishability obfuscator if and only if it satisfies both of the following two statements: [5] [6] [7]

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 NC0. [5] (The existence of pseudorandom generators in NC0 (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 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]

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:

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]

See also

Related Research Articles

In software development, obfuscation is the act of creating source or machine code that is difficult for humans or computers to understand. Like obfuscation in natural language, it may use needlessly roundabout expressions to compose statements. Programmers may deliberately obfuscate code to conceal its purpose or its logic or implicit values embedded in it, primarily, in order to prevent tampering, deter reverse engineering, or even to create a puzzle or recreational challenge for someone reading the source code. This can be done manually or by using an automated tool, the latter being the preferred technique in industry.

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 or zero-knowledge protocol is a method by which one party can prove to another party that a given statement is true, while avoiding conveying to the verifier any information beyond the mere fact of the statement's truth. The intuition underlying zero-knowledge proofs is that it is trivial to prove the possession of certain information by simply revealing it; the challenge is to prove this possession without revealing the information, or any aspect of it whatsoever.

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 out-sourced 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 .

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.

<span class="mw-page-title-main">Amit Sahai</span> American cryptographer (born 1974)

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. 1 2 Klarreich, Erica (2014-02-03). "Cryptography Breakthrough Could Make Software Unhackable". Quanta Magazine.
  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.
  3. 1 2 3 4 5 6 7 8 Klarreich, Erica (2020-10-10). "Computer Scientists Achieve 'Crown Jewel' of Cryptography". Quanta Magazine.
  4. 1 2 Barak, Boaz (29 December 2020). "New Developments in Indistinguishability Obfuscation (iO) | Simons Institute for the Theory of Computing". simons.berkeley.edu. Retrieved 22 August 2021.
  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 .
  6. 1 2 Moran, Tal; Rosen, Alon (7 October 2013). "There is no Indistinguishability Obfuscation in Pessiland" (PDF). IACR Cryptology ePrint Archive.
  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.
  8. 1 2 Klarreich, Erica (2014-01-30). "Perfecting the Art of Sensible Nonsense". Quanta Magazine. Retrieved 2021-08-22.
  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.
  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.
  11. 1 2 Sanjam Garg; Craig Gentry; Shai Halevi; Mariana Raykova; Amit Sahai; Brent Waters (2013). "Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE. pp. 40–49. CiteSeerX   10.1.1.672.1968 . doi:10.1109/FOCS.2013.13. ISBN   978-0-7695-5135-7. S2CID   15703414.{{cite book}}: |journal= ignored (help)
  12. ↑ Applebaum, B; Ishai, Y; Kushilevitz, E (2006). "Cryptography in NC0" (PDF). SIAM Journal on Computing. 36 (4): 845–888. doi:10.1137/S0097539705446950.
  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 . 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.
  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.
  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.
  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.
  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.
  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.
  20. ↑ Asharov, Gilad; Segev, Gil (2015). "Limits on the Power of Indistinguishability Obfuscation and Functional Encryption". Cryptology ePrint Archive.
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.