## CryptoDB

### Paper: How to Leverage Hardness of Constant-Degree Expanding Polynomials over $\mathbb {R}$R to build $i\mathcal {O}$iO

Authors: Aayush Jain Huijia Lin Christian Matt Amit Sahai DOI: 10.1007/978-3-030-17653-2_9 (login may be required) Search ePrint Search Google In this work, we introduce and construct D-restricted Functional Encryption (FE) for any constant $D \ge 3$D≥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)$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=(\varvec{x},\varvec{y},\varvec{z})$M=(x,y,z). Here, $\varvec{x}\in \mathbb {F}_{\mathbf {p}}^{d\times n}$x∈Fpd×n and $\varvec{y},\varvec{z}\in \mathbb {F}_{\mathbf {p}}^n$y,z∈Fpn. Function keys can be issued for a function $f=\varSigma _{\varvec{I}= (i_1,..,i_d,j,k)}\ c_{\varvec{I}}\cdot \varvec{x}[1,i_1] \cdots \varvec{x}[d,i_d] \cdot \varvec{y}[j]\cdot \varvec{z}[k]$f=ΣI=(i1,..,id,j,k)cI·x[1,i1]⋯x[d,id]·y[j]·z[k] where the coefficients $c_{\varvec{I}}\in \mathbb {F}_{\mathbf {p}}$cI∈Fp. Knowing the function key and the ciphertext, one can learn $f(\varvec{x},\varvec{y},\varvec{z})$f(x,y,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 $\varvec{y}$y and $\varvec{z}$z, although it is not required to hide $\varvec{x}$x. Thus $\varvec{x}$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}$R. In particular, we build upon the work of Ananth et al. to show how to build indistinguishability obfuscation ($i\mathcal {O}$iO) assuming only SXDH over bilinear groups, LWE, and assumptions relating to weak pseudorandom properties of constant-degree expanding polynomials over $\mathbb {R}$R.
##### BibTeX
@article{eurocrypt-2019-29337,
title={How to Leverage Hardness of Constant-Degree Expanding Polynomials over $\mathbb {R}$R to build $i\mathcal {O}$iO},
booktitle={Advances in Cryptology – EUROCRYPT 2019},
series={Advances in Cryptology – EUROCRYPT 2019},
publisher={Springer},
volume={11476},
pages={251-281},
doi={10.1007/978-3-030-17653-2_9},
author={Aayush Jain and Huijia Lin and Christian Matt and Amit Sahai},
year=2019
}