Abstract
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 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⁰ with stretch n^1+τ, Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.