Welcome to the resource topic for 2021/1334
Title:
Indistinguishability Obfuscation from LPN over F_p, DLIN, and PRGs in NC^0
Authors: Aayush Jain, Huijia Lin, Amit Sahai
Abstract:In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation (i\mathcal{O}). We prove: {\bf Theorem}(Informal): Assume sub-exponential security of the following assumptions: - the Learning Parity with Noise (\mathsf{LPN}) assumption over general prime fields \mathbb{F}_p with polynomially many \mathsf{LPN} samples and error rate 1/k^\delta, where k is the dimension of the \mathsf{LPN} secret, and \delta>0 is any constant; - the existence of a Boolean Pseudo-Random Generator (\mathsf{PRG}) in \mathsf{NC}^0 with stretch n^{1+\tau}, where n is the length of the \mathsf{PRG} seed, and \tau>0 is any constant; - the Decision Linear (\mathsf{DLIN}) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.} This removes the reliance on the Learning With Errors (LWE) assumption from the recent work of [Jain, Lin, Sahai STOC’21]. As a consequence, we obtain the first fully homomorphic encryption scheme that does not rely on any lattice-based hardness assumption. Our techniques feature a new notion of randomized encoding called Preprocessing Randomized Encoding (PRE) that, essentially, can be computed in the exponent of pairing groups. When combined with other new techniques, PRE gives a much more streamlined construction of \iO while still maintaining reliance only on well-studied assumptions.
ePrint: https://eprint.iacr.org/2021/1334
Talk: https://www.youtube.com/watch?v=UbHotFvBMRM
Slides: https://iacr.org/submit/files/slides/2022/eurocrypt/eurocrypt2022/170/slides.pdf
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 .