Candidate Obfuscation via Oblivious LWE Sampling
Hoeteck Wee, Daniel Wichs
Abstract
We present a new, simple candidate construction of indistinguishability obfuscation (iO). Our scheme is inspired by lattices and learning-with-errors (LWE) techniques, but we are unable to prove security under a standard assumption. Instead, we formulate a new falsifiable assumption under which the scheme is secure. Furthermore, the scheme plausibly achieves post-quantum security.
Our construction is based on the recent "split FHE" framework of Brakerski, D öttling, Garg, and Malavolta (EUROCRYPT '20), and we provide a new instantiation of this framework. As a first step, we construct an iO scheme that is provably secure assuming that LWE holds and that it is possible to obliviously generate LWE samples without knowing the corresponding secrets. We define a precise notion of oblivious LWE sampling that suffices for the construction. It is known how to obliviously sample from any distribution (in a very strong sense) using iO, and our result provides a converse, showing that the ability to obliviously sample from the specific LWE distribution (in a much weaker sense) already also implies iO. As a second step, we give a heuristic contraction of oblivious LWE sampling. On a very high level, we do this by homomorphically generating pseudorandom LWE samples using an encrypted pseudorandom function.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
18 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices cites Indistinguishability obfuscation from circular security
- Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices cites Indistinguishability obfuscation from well-founded assumptions
- Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices cites Candidate Witness Encryption from Lattice Techniques
- Hidden Cosets and Applications to Unclonable Cryptography cites Indistinguishability obfuscation from well-founded assumptions
- Hidden Cosets and Applications to Unclonable Cryptography cites Secure Software Leasing
- Indistinguishability obfuscation from well-founded assumptions cites Candidate iO from Homomorphic Encryption Schemes
- Indistinguishability obfuscation from well-founded assumptions cites Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification
- Indistinguishability obfuscation from well-founded assumptions cites Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE
- Classical vs Quantum Random Oracles cites Indistinguishability obfuscation from circular security
- Classical vs Quantum Random Oracles cites Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE
- Candidate Witness Encryption from Lattice Techniques cites Indistinguishability obfuscation from well-founded assumptions
- Candidate Witness Encryption from Lattice Techniques cites Candidate iO from Homomorphic Encryption Schemes
- Candidate Witness Encryption from Lattice Techniques cites Indistinguishability Obfuscation from Simple-to-State Hard Problems: New Assumptions, New Techniques, and Simplification
- Secure Software Leasing cites Indistinguishability obfuscation from circular security
Cited by top-tier papers18
- Hidden Cosets and Applications to Unclonable CryptographyAndrea Coladangelo, Jiahui Liu, Qipeng Liu, Mark ZhandryCRYPTO 2021 · 64 citations
- Candidate Witness Encryption from Lattice TechniquesRotem TsabaryCRYPTO 2022 · 61 citations
- Secure Software LeasingPrabhanjan Ananth, Rolando L. La PlacaEUROCRYPT 2021 · 51 citations
- Classical vs Quantum Random OraclesTakashi Yamakawa, Mark ZhandryEUROCRYPT 2021 · 43 citations
- Attribute-Based Encryption for Circuits of Unbounded Depth from LatticesYao-Ching Hsieh, Huijia Lin, Ji LuoFOCS 2023 · 38 citations
Builds on5
- Indistinguishability obfuscation from well-founded assumptionsAayush Jain, Huijia Lin, Amit SahaiSTOC 2021 · 223 citations
- Indistinguishability obfuscation from circular securityRomain Gay, Rafael PassSTOC 2021 · 78 citations
- Candidate iO from Homomorphic Encryption SchemesZvika Brakerski, Nico Döttling, Sanjam Garg, Giulio MalavoltaEUROCRYPT 2020 · 60 citations
- Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FEShweta Agrawal, Alice Pellet-MaryEUROCRYPT 2020 · 51 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
Related papers
- Lattice-Based Obfuscation from NTRU and Equivocal LWEValerio Cini, Russell W. F. Lai, Ivy K. Y. WooCRYPTO 2025 · 3 citations
- Counterexamples to New Circular Security Assumptions Underlying iOSamuel B. Hopkins, Aayush Jain, Huijia LinCRYPTO 2021 · 28 citations
- Indistinguishability Obfuscation from LPN over , DLIN, and PRGs in NC0Aayush Jain, Huijia Lin, Amit SahaiEUROCRYPT 2022 · 102 citations
- Pseudorandom Obfuscation and ApplicationsPedro Branco, Nico Döttling, Abhishek Jain, Giulio Malavolta et al.CRYPTO 2025 · 6 citations
- Obfuscation of Pseudo-Deterministic Quantum CircuitsJames Bartusek, Fuyuki Kitagawa, Ryo Nishimaki, Takashi YamakawaSTOC 2023 · 23 citations
