Paper 2018/646
Pseudo FlawedSmudging Generators and Their Application to Indistinguishability Obfuscation
Huijia Lin and Christian Matt
Abstract
We introduce Pseudo Flawedsmudging Generators (PFGs). A PFG is an expanding function whose outputs $\mathbf Y$ satisfy a weak form of pseudorandomness. Roughly speaking, for some polynomial bound $B$, and every distribution $\chi$ over $B$bounded noise vectors, it guarantees that the distribution of $(\mathbf e,\ \mathbf Y + \mathbf e)$ is indistinguishable from that of $(\mathbf e', \mathbf Y + \mathbf e)$, where $\mathbf e \gets \chi$ is a random sample from $\chi$, and $\mathbf e'$ is another independent sample from $\chi$ conditioned on agreeing with $\mathbf e$ at a few, $o(\lambda)$, coordinates. In other words, $\mathbf Y$ "hides" $\mathbf e$ at all but a few coordinates. We show that assuming LWE and the existence of constantlocality PseudoRandom Generators (PRGs), there is a construction of IO from 1) a PFG that has polynomial stretch and polynomially bounded outputs, and 2) a Functional Encryption (FE) scheme able to compute this PFG. Such FE can be built from degree $d$ multilinear map if the PFG is computable by a degree $d$ polynomial. Toward basing IO on bilinear maps, inspired by [Ananth et. al. Eprint 2018], we further consider PFGs with partial pubic input  they have the form $g(\mathbf{x}, \mathbf{y})$ and satisfy the aforementioned pseudo flawedsmudging property even when $\mathbf{x}$ is public. When using such PFGs, it suffices to replace FE with a weaker notion of partially hiding FE (PHFE) whose decryption reveals the public input $\mathbf{x}$ in addition to the output of the computation. We construct PHFE for polynomials $g$ that are quadratic in the private input $\mathbf{y}$, but have up to polynomial degree in the public input $\mathbf{x}$, subject to certain size constraints, from the SXDH assumption over bilinear map groups. Regarding candidates of PFGs with partial public input, we note that the family of cubic polynomials proposed by Ananth et. al. can serve as candidate PFGs, and can be evaluated by our PHFE from bilinear maps. Toward having more candidates, we present a transformation for converting the private input $\mathbf{x}$ of a constantdegree PFG $g(\mathbf{x}, \mathbf{y})$ into a public input, by hiding $\mathbf{x}$ as noises in LWE samples, provided that $\mathbf{x}$ is sampled from a LWE noise distribution and $g$ satisfies a stronger security property.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 indistinguishability obfuscationfunctional encryptionpseudorandomness
 Contact author(s)
 cmatt @ cs ucsb edu
 History
 20181009: revised
 20180706: received
 See all versions
 Short URL
 https://ia.cr/2018/646
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/646, author = {Huijia Lin and Christian Matt}, title = {Pseudo FlawedSmudging Generators and Their Application to Indistinguishability Obfuscation}, howpublished = {Cryptology ePrint Archive, Paper 2018/646}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/646}}, url = {https://eprint.iacr.org/2018/646} }