# Indistinguishability Obfuscation from Well-Founded Assumptions

arXiv: https://arxiv.org/abs/2008.09317 · HTML: https://mlsanity.com/paper/2008.09317/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2020.

## Built on by (most cited first, 12 of 12)

- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [SLIP: Securing LLMs IP Using Weights Decomposition](https://mlsanity.com/paper/2407.10886/) (2024)
- [Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs](https://mlsanity.com/paper/2201.07206/) (2022)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)
- [Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models](https://mlsanity.com/paper/2406.05660/) (2024)
- [Spoofing Generalization: When Can't You Trust Proprietary Models?](https://mlsanity.com/paper/2106.08393/) (2021)
- [Backdoor defense, learnability and obfuscation](https://mlsanity.com/paper/2409.03077/) (2024)
- [Mitigating Adversarial Attacks by Distributing Different Copies to Different Users](https://mlsanity.com/paper/2111.15160/) (2021)
- [On the Hardness of Learning One Hidden Layer Neural Networks](https://mlsanity.com/paper/2410.03477/) (2024)
- [Statistically Undetectable Backdoors in Deep Neural Networks](https://mlsanity.com/paper/2607.09532/) (2026)
- [One Picture is Worth a Thousand Words: A New Wallet Recovery Process](https://mlsanity.com/paper/2205.02511/) (2022)
- [Cheap to Hypothesize, Costly to Verify: The Defense Surface of Agentic Vulnerability Discovery](https://mlsanity.com/paper/2609.35909/) (2026)

## Abstract (arXiv)

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.