Paper 2021/1334

Indistinguishability Obfuscation from LPN over F_p, DLIN, and PRGs in NC^0

Aayush Jain, Huijia Lin, and Amit Sahai


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Indistinguishability ObfuscationHomomorphic Encryption
Contact author(s)
aayushjain1728 @ gmail com
rachel @ cs washington edu
sahai @ cs ucla edu
2021-10-05: revised
2021-10-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aayush Jain and Huijia Lin and Amit Sahai},
      title = {Indistinguishability Obfuscation from {LPN} over F_p, {DLIN}, and {PRGs} in {NC}^0},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1334},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.