Indistinguishability obfuscation from well-founded assumptions

In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Theorem (Informal). Let τ ∈ (0, ∞), δ ∈ (0, 1), ǫ ∈ (0, 1) be arbitrary constants. Assume sub-exponential security of the following assumptions, where λ is a security parameter, and the parameters ℓ, k, n below are large enough polynomials in λ:

• the SXDH assumption on asymmetric bilinear groups of a prime order p = O(2 λ ),

• the LWE assumption over Z p with subexponential modulus-to-noise ratio 2 k ǫ , where k is the dimension of the LWE secret,

• the LPN assumption over Z p with polynomially many LPN samples and error rate 1/ℓ δ , where ℓ is the dimension of the LPN secret,

• the existence of a Boolean PRG in NC 0 with stretch n 1+τ , Then, (subexponentially secure) indistinguishability obfuscation for all polynomialsize circuits exists.

Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomialsize circuits.