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: 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 mathbbZp with subexponential modulus-to-noise ratio 2kε, where k is the dimension of the LWE secret, - The LPN assumption over mathbbZp with polynomially many LPN samples and error rate 1/ℓδ, where ℓ is the dimension of the LPN secret, - The existence of a Boolean PRG in mathsfNC0 with stretch n1+τ, Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.