Welcome to the resource topic for 2018/646
Title:
Pseudo Flawed-Smudging Generators and Their Application to Indistinguishability Obfuscation
Authors: Huijia Lin, Christian Matt
Abstract: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.
ePrint: https://eprint.iacr.org/2018/646
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .