UCLA

Program Obfuscation is the art of making computer programs ``unintelligible" while preserving its functionality. There have been many attempts to formalize this notion and one such formalization, termed as indistinguishability obfuscation (iO),

has led to several powerful implications: game theoretic hardness results, watermarking of programs, feasibility of time-lock puzzles, advanced encryption systems, leakage resilient circuit compilers, succinct randomized encodings and so on.

On the construction side, in spite of intense research, the problem of basing iO on standard falsifiable cryptographic assumptions remains open. All the current known constructions of iO are based on the tool of degree-$d$ multilinear maps. The candidates for degree-$d$ multilinear maps, for arbitrary $d$, were only recently studied and its associated assumptions have been subject to several devastating cryptanalytic attacks. On the other hand, there are no known attacks on the candidates of degree-2 multilinear maps (also known bilinear maps), even after a decade of cryptanalytic research.

The original construction of iO proposed by Garg, Gentry, Halevi, Raykova, Sahai in 2013 required degree-$d$ multilinear maps, where $d$ was a large polynomial in the security parameter. Although the works that followed improved the original work in different aspects, they still relied on $d$ to be a large polynomial in the security parameter.

In this thesis, we (jointly with Jain, CRYPTO 2015) first propose a new template to construct iO starting from functional encryption, a primitive that has been explored for over a decade. Subsequently, several works used this template to construct iO. Notably, Lin (EUROCRYPT 2016) and subsequently Lin and Vaikuntanathan (FOCS 2016) showed how to construct iO relying upon degree-$d$ multilinear maps and other relatively mild assumptions, where $d$ is a constant ($> 30$). We (jointly with Sahai, EUROCRYPT 2017) improve upon these works and show how to base iO relying upon degree-5 multilinear maps and other relatively mild assumptions. This brings us tantalizingly close to basing iO on bilinear maps.