Paper 2019/1252
Simplifying Constructions and Assumptions for $i\mathcal{O}$
Aayush Jain, Huijia Lin, and Amit Sahai
Abstract
The existence of secure indistinguishability obfuscators ($i\mathcal{O}$) has farreaching 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 $i\mathcal{O}$~from simpler building blocks, and represents the state of the art in constructing $i\mathcal{O}$~from succinct and instanceindependent assumptions. This line of work has culminated in a construction of $i\mathcal{O}$~from four assumptions, consisting of two standard assumptions, namely subexponentially secure LWE and SXDH over bilinear groups, and two other pseudorandomness assumptions: The first assumes weak pseudorandomness properties of generators computable by constantdegree polynomials over the integers, as well as an 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: \begin{itemize} \item We completely remove the need to assume a constantblock local PRG. This yields a construction of $i\mathcal{O}$ based on three assumptions of LWE, SXDH and a constant degree perturbation resilient generator [Jain, Lin, Matt, and Sahai, 2019] \item 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}^0$, from Ring LWE [Agrawal and Rosen, 2017]. Our new SHE allows our construction of $i\mathcal{O}$ 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. \item Finally, we investigate a main technical concept facilitating the line of work on $i\mathcal{O}$; namely the notion of \emph{partially hiding functional encryption} introduced by [Ananth, Jain, and Sahai 2018]. The partially hiding functional encryption used in these $i\mathcal{O}$ 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 ciphertext 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]. \end{itemize}
Note: Fixed some typos.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Indistinguishability Obfuscation
 Contact author(s)

aayushjain @ cs ucla edu
rachel @ cs washington edu
sahai @ cs ucla edu  History
 20191224: last of 2 revisions
 20191028: received
 See all versions
 Short URL
 https://ia.cr/2019/1252
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1252, author = {Aayush Jain and Huijia Lin and Amit Sahai}, title = {Simplifying Constructions and Assumptions for $i\mathcal{O}$}, howpublished = {Cryptology ePrint Archive, Paper 2019/1252}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/1252}}, url = {https://eprint.iacr.org/2019/1252} }