Pseudo Flawed-Smudging Generators and Their Application to Indistinguishability Obfuscation
Huijia Lin and Christian Matt
Abstract
We introduce Pseudo Flawed-smudging Generators (PFGs). A PFG is an expanding function whose outputs satisfy a weak form of pseudo-randomness. Roughly speaking, for some polynomial bound , and every distribution over -bounded noise vectors, it guarantees that the distribution of is indistinguishable from that of , where is a random sample from , and is another independent sample from conditioned on agreeing with at a few, , coordinates. In other words, "hides" 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 multilinear map if the PFG is computable by a degree 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 and satisfy the aforementioned pseudo flawed-smudging property even when 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 in addition to the output of the computation. We construct PHFE for polynomials that are quadratic in the private input , but have up to polynomial degree in the public input , 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 of a constant-degree PFG into a public input, by hiding as noises in LWE samples, provided that is sampled from a LWE noise distribution and satisfies a stronger security property.
@misc{cryptoeprint:2018/646,
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},
url = {https://eprint.iacr.org/2018/646}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.