Paper 2018/973
How to leverage hardness of constantdegree expanding polynomials over $\mathbb{R}$ to build iO
Aayush Jain and Amit Sahai
Abstract
In this work, we introduce and construct $D$restricted Functional Encryption (FE) for any constant $D \ge 3$, based only on the SXDH assumption over bilinear groups. This generalizes the notion of $3$restricted FE recently introduced and constructed by Ananth et al. (ePrint 2018) in the generic bilinear group model. A $D=(d+2)$restricted FE scheme is a secret key FE scheme that allows an encryptor to efficiently encrypt a message of the form $M=(\vec{x},\vec{y},\vec{z})$. Here, $\vec{x}\in \F_{\prm}^{d\times n}$ and $\vec{y},\vec{z}\in \F_{\prm}^n$. Function keys can be issued for a function $f=\Sigma_{\vec{I}= (i_1,..,i_d,j,k)}\ c_{\vec{I}}\cdot \vec{x}[1,i_1] \cdots \vec{x}[d,i_d] \cdot \vec{y}[j]\cdot \vec{z}[k]$ where the coefficients $c_{\vec{I}}\in \F_{\prm}$. Knowing the function key and the ciphertext, one can learn $f(\vec{x},\vec{y},\vec{z})$, if this value is bounded in absolute value by some polynomial in the security parameter and $n$. The security requirement is that the ciphertext hides $\vec{y}$ and $\vec{z}$, although it is not required to hide $\vec{x}$. Thus $\vec{x}$ can be seen as a public attribute. $D$restricted FE allows for useful evaluation of constantdegree polynomials, while only requiring the SXDH assumption over bilinear groups. As such, it is a powerful tool for leveraging hardness that exists in constantdegree expanding families of polynomials over $\mathbb{R}$. In particular, we build upon the work of Ananth et al. to show how to build indistinguishability obfuscation (iO) assuming only SXDH over bilinear groups, LWE, and assumptions relating to weak pseudorandom properties of constantdegree expanding polynomials over $\mathbb{R}$.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Indistinguishability Obfuscation
 Contact author(s)

aayushjain @ cs ucla edu
sahai @ cs ucla edu  History
 20181015: received
 Short URL
 https://ia.cr/2018/973
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/973, author = {Aayush Jain and Amit Sahai}, title = {How to leverage hardness of constantdegree expanding polynomials over $\mathbb{R}$ to build iO}, howpublished = {Cryptology ePrint Archive, Paper 2018/973}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/973}}, url = {https://eprint.iacr.org/2018/973} }