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

Aayush Jain; Huijia Lin; Amit Sahai

Cryptology ePrint Archive: Report 2019/1252

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

Aayush Jain and Huijia Lin and Amit Sahai

Abstract: The existence of secure indistinguishability obfuscators ($i\mathcal{O}$) 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 $i\mathcal{O}$~from simpler building blocks, and represents the state of the art in constructing $i\mathcal{O}$~from succinct and instance-independent assumptions. This line of work has culminated in a construction of $i\mathcal{O}$~from four assumptions, consisting of two standard assumptions, namely sub-exponentially secure LWE and SXDH over bilinear groups, and two other pseudorandomness assumptions: The first assumes weak pseudorandomness properties of generators computable by constant-degree 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 constant-block 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 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]. \end{itemize}

Category / Keywords: public-key cryptography / Indistinguishability Obfuscation

Date: received 25 Oct 2019, last revised 24 Dec 2019

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