UCLA

Can we efficiently compile a computer program P into another one say \tilde{P}, which has the same functionality as P on every input, but otherwise is as unintelligible as possible? This question was asked in 1976 by the Turing award winning work of Diffie-Hellman (STOC 1976). Such a compiler is called as Obfuscation. It is not hard to see that such a notion will find lots of application so much so that today it is one of the most versatile primitives in cryptography. The work of Barak et. al. (Crypto 2001) and Goldwasser and Rothblum (TCC 2007) established that in order to construct an obfuscation scheme which provides best possible unintelligibility guarantees, it suffices to construct what is called as an Indistinguishibility Obfuscation (iO) scheme. An iO scheme is an obfuscation scheme that only hides implementation differences. Such a scheme guarantees that for every two programs P_0,P_1 of the same description size, same running time having the same input output behavior, but otherwise having different internal details iO(P_0) is indistinguishabile to iO(P_1). Unfortunately, up until now it was not clear if such a primitive can even exist. All the known constructions were heuristic, based on newly stated assumptions, and most of the times subject to cycles of attacks and fixes. In this thesis, we present the first feasibility result of an obfuscation scheme by constructing an obfuscation scheme from well-studied cryptographic assumptions. We prove:

Theorem: (Jain-Lin-Sahai STOC 2021, Jain-Lin-Sahai 2021b) Assume sub-exponential security of the following assumptions:

- the Learning Parity with Noise (LPN) assumption over general prime fields Z_p with polynomially many LPN samples and error rate 1/k^\delta, where k is the dimension of the LPN secret, and \delta>0 is any constant; - the existence of a Boolean Pseudo-Random Generator (PRG) in NC^0 with stretch n^{1+\tau}, where n is the length of the PRG seed, and \tau>0 is any constant;

- the Decision Linear (DLIN) assumption on symmetric bilinear groups of prime order.

Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.

All the three assumptions are based on computational problems with a long history of study, rooted in complexity, coding, and number theory. As a corollary this gives feasibility results for many of the other cryptographic primitives that had remained elusive and are known to follow from iO, from the same set of assumptions. Our work also gives rise to the first construction of a fully-homomorphic encryption scheme that does not rely on the hardness of a lattice based problem.

This work is a culmination of a line of work spanning multiple years \cite{AJS18,C:AJLMS19,EC:JLMS19,EC:BHJKS19,EC:GJLS21,STOC:JaiLinSah21,JLS21b}. This line introduced many different intermediate building blocks relying on a number of concepts in cryptography. These blocks were simplified and built upon in subsequent works. In this thesis, we present a self contained, simplified and streamlined construction largely adapted from \cite{JLS21b} but borrowing elements from some of the works mentioned above.