You are looking at a specific version 20190911:073127 of this paper. See the latest version.

Paper 2019/1030

How to leverage hardness of constant degree expanding polynomials over R to build iO

Aayush Jain and Huijia Lin and Christian Matt 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_{p}^{d\times n}$ and $\vec{y},\vec{z}\in F_{p}^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_{p}$. 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 constant-degree polynomials, while only requiring the SXDH assumption over bilinear groups. As such, it is a powerful tool for leveraging hardness that exists in constant-degree 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 constant-degree expanding polynomials over $\mathbb{R}$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. EUROCRYPT 2019
Keywords
Obfuscation
Contact author(s)
aayushjain1728 @ gmail com,huijial @ gmail com,cm @ concordium com,sahai @ cs ucla edu
History
2019-09-11: received
Short URL
https://ia.cr/2019/1030
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.