Indistinguishability Obfuscation from LPN over , DLIN, and PRGs in NC0
Aayush Jain, Huijia Lin, Amit Sahai
Abstract
In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation (). We prove:
Theorem(Informal): Assume sub-exponential security of the following assumptions:
-
the Learning Parity with Noise () assumption over general prime fields with polynomially many samples and error rate , where is the dimension of the secret, and is any constant;
-
the existence of a Boolean Pseudo-Random Generator () in with stretch , where is the length of the seed, and is any constant;
-
the Decision Linear () assumption on symmetric bilinear groups of prime order.
Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.
This removes the reliance on the Learning With Errors (LWE) assumption from the recent work of [Jain, Lin, Sahai STOC'21]. As a consequence, we obtain the first fully homomorphic encryption scheme that does not rely on any lattice-based hardness assumption.
Our techniques feature a new notion of randomized encoding called Preprocessing Randomized Encoding (PRE) that, essentially, can be computed in the exponent of pairing groups. When combined with other new techniques, PRE gives a much more streamlined construction of while still maintaining reliance only on well-studied assumptions.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
6 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
its abstract · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers6
- Registered Attribute-Based EncryptionSusan Hohenberger, George Lu, Brent Waters, David J. WuEUROCRYPT 2023 · 83 citations
- Quantum State Obfuscation from Classical OraclesJames Bartusek, Zvika Brakerski, Vinod VaikuntanathanSTOC 2024 · 17 citations
- NP-Hardness of Approximating Meta-Complexity: A Cryptographic ApproachYizhi Huang, Rahul Ilango, Hanlin RenSTOC 2023 · 6 citations
- Hardness of Range Avoidance and Remote Point for Restricted Circuits via CryptographyYilei Chen, Jiatu LiSTOC 2024 · 4 citations
- Quartic quantum speedups for planted inferenceAlexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan BabbushSODA 2025 · 1 citation
Related papers
- Indistinguishability obfuscation from well-founded assumptionsAayush Jain, Huijia Lin, Amit SahaiSTOC 2021 · 223 citations
- Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and SimplificationRomain Gay, Aayush Jain, Huijia Lin, Amit SahaiEUROCRYPT 2021 · 46 citations
- Indistinguishability obfuscation from circular securityRomain Gay, Rafael PassSTOC 2021 · 78 citations
- Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FEShweta Agrawal, Alice Pellet-MaryEUROCRYPT 2020 · 51 citations
- Pseudorandom Obfuscation and ApplicationsPedro Branco, Nico Döttling, Abhishek Jain, Giulio Malavolta et al.CRYPTO 2025 · 6 citations
