Indistinguishability Obfuscation from Well-Founded Assumptions
share
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 ℤ_p with subexponential modulus-to-noise ratio 2^k^ϵ, where k is the dimension of the LWE secret, - The LPN assumption over ℤ_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 𝖭𝖢^0 with stretch n^1+τ, Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.
READ FULL TEXT