Abstract
In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation (\(i\mathcal {O}\)). We prove:
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 \(i\mathcal {O}\) while still maintaining reliance only on well-studied assumptions.