Paper 2018/646

Pseudo Flawed-Smudging Generators and Their Application to Indistinguishability Obfuscation

Huijia Lin and Christian Matt


We introduce Pseudo Flawed-smudging Generators (PFGs). A PFG is an expanding function whose outputs $\mathbf Y$ satisfy a weak form of pseudo-randomness. 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 constant-locality Pseudo-Random 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 flawed-smudging 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 constant-degree 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.

Available format(s)
Publication info
Preprint. MINOR revision.
indistinguishability obfuscationfunctional encryptionpseudo-randomness
Contact author(s)
cmatt @ cs ucsb edu
2018-10-09: revised
2018-07-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Huijia Lin and Christian Matt},
      title = {Pseudo Flawed-Smudging Generators and Their Application to Indistinguishability Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/646},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.