**Simplifying Constructions and Assumptions for $i\mathcal{O}$**

*Aayush Jain and Huijia Lin and Amit Sahai*

**Abstract: **The existence of secure indistinguishability obfuscators ($iO$) has
far-reaching implications, significantly expanding the scope of
problems amenable to cryptographic study. A recent line of work
[Ananth, Jain, and Sahai, 2018; Aggrawal, 2018; Lin and Matt, 2018;
Jain, Lin, Matt, and Sahai, 2019] has developed a new theory for
building $iO$~from simpler building blocks, and represents the state
of the art in constructing $iO$~from succinct and
instance-independent assumptions. This line of work has culminated
in a construction of $iO$~from four assumptions, consisting of two
standard assumptions, namely sub-exponentially secure LWE and SXDH
over bilinear groups, and two relatively new assumptions: The first
assumes weak pseudorandomness properties of generators computable by
constant-degree polynomials over the integers, as well as a LWE
leakage assumption, introduced by [Jain, Lin, Matt, and Sahai, 2019]. The second assumes the existence of Boolean PRGs with constant block locality [Goldreich 2000, Lin and Tessaro 2017]. In this work, we make the following contributions:

* We completely remove the need of one of the two non-standard assumptions mentioned above; namely we no longer need to assume a constant-block local PRG. This yields a construction of $iO$ based on three assumptions of LWE, SXDH and a constant degree perturbation resilient generator [Jain, Lin, Matt, and Sahai, 2019]

* Our construction is arguably simpler and more direct than previous constructions. We construct the notion of special homomorphic encoding (SHE) for all $P/poly$ from LWE, by adapting techniques from Predicate Encryption [Gorbunov, Vaikunthanathan and Wee, 2015]. Prior to our work, SHE was only known for the class $\mathsf{NC}^1$, from Ring LWE [Agrawal and Rosen, 2017]. Our new SHE allows our construction of $iO$ to avoid an intermediate step of bootstrapping via randomized encodings. Indeed, we construct a functional encryption scheme whose ciphertext grows sublinearly only in the output length of the circuits as opposed to its size. This is first such scheme that does not rely on multilinear maps.

* Finally, we investigate a main technical concept facilitating the line of work on $iO$; namely the notion of partially hiding functional encryption introduced by [Ananth, Jain, and Sahai 2018]. The partially hiding functional encryption used in these $iO$ constructions allows an encryptor to encrypt vectors of the form $\vec{x},\vec{y},\vec{z} \in \mathbb{Z}^n_{p}$ and allows any decrptor with a key for function $f$ to learn $\langle f(\vec{x}), \vec{y}\otimes \vec{z} \rangle$. The encryption is allowed to reveal $\vec{x}$ while keeping $\vec{y},\vec{z}$ hidden. Furthermore, the size of the cipher-text should grow linearly in $n$.

We significantly improve the starte of the art for partially hiding functional encryption: Assuming SXDH over bilinear maps, we construct a partially hiding FE scheme where the function $f$ is allowed to be any polynomial sized arithmetic branching program. Prior to our work, the best partially hiding FE only supported the class of constant degree polynomials over $\mathbb{Z}_{p}$ [Jain, Lin, Matt, and Sahai 2019].

**Category / Keywords: **public-key cryptography / Indistinguishability Obfuscation

**Date: **received 25 Oct 2019

**Contact author: **aayushjain at cs ucla edu,rachel@cs washington edu,sahai@cs ucla edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20191028:082642 (All versions of this report)

**Short URL: **ia.cr/2019/1252

[ Cryptology ePrint archive ]