Indistinguishability Obfuscation from Well-Founded Assumptions

2020/08/21 by Aayush Jain, Jain, Aayush, Huijia Lin +3 · 1 voice · 4 citations
#cs.CR #cs.CC

paper · pdf · doi:10.48550/arxiv.2008.09317

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

Cited by

• Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
• Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
• SLIP-SEC: Formalizing Secure Protocols for Model IP Protection
• Improved Search-to-Decision Reduction for Random Local Functions

Discussions

• Indistinguishability Obfuscation from Well-Founded Assumptions [lobsters, 8 points, 2 comments]

Related

• Indistinguishability Obfuscation of Circuits and its Application in Security
• The impossibility of obfuscation with auxiliary input or a universal simulator
• Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP
• The Quasi-Polynomial Low-Degree Conjecture is False
• Deciding Indistinguishability