Abstract
Lattice problems and techniques are quintessential in realizing advanced cryptographic primitives that involve complex computations over secret values. In this work, we depart from the lattice paradigm, and show that indistinguishability obfuscation can be constructed without lattices! We prove:
Theorem: Assume sub-exponential security of the following assumptions:
- the Learning Parity with Noise ($\mathsf{LPN}$) assumption over general prime fields $\mathbb{Z}_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 our previous construction [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-founded assumptions.
Joint work with Aayush Jain and Huijia Lin.