Indistinguishability obfuscation from well-founded assumptions
Open accessThe DOI matches its Crossref record; 59 of the 59 references it cites were found in a registry or an index.
Abstract
Indistinguishability obfuscation, introduced by [Barak et. al. Crypto 2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove:
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Trapdoors for hard lattices and new cryptographic constructions
Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374407 · Cited by 2,435 · cited 1×
“The work of [38] proved the security of a similar construction based on a new variant of the 2-circular SRL security assumption proposed by [69], with respect to GSW and a packed variant of the dual-Regev encryption scheme [70], which requires SRL security to hold in the presence of a length-2 chain of circular encryp…”
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060603 · Cited by 2,313 · cited 1×
“This assumption was first stated in the work of [110].”
Boneh, D., Boyen, X., & Shacham, H. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-28628-8_3 · Cited by 2,089 · cited 2×
“Then, the DLIN assumption requires that the following computational indistinguishability holds: {( 𝑔𝑥 , 𝑔𝑦, 𝑔𝑥𝑟 , 𝑔𝑦𝑠 , 𝑔𝑟+𝑠 ) | 𝑥,𝑦, 𝑟, 𝑠 ← Z𝑝 } ≈𝑐 {( 𝑔𝑥 , 𝑔𝑦, 𝑔𝑥𝑟 , 𝑔𝑦𝑠 , 𝑔𝑧 ) | 𝑥,𝑦, 𝑟, 𝑠, 𝑧 ← Z𝑝 } This assumption was first introduced in the 2004 work of Boneh, Boyen, and Shacham [30].”
(Leveled) fully homomorphic encryption without bootstrapping
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090262 · Cited by 1,782
Gentry, C., Sahai, A., & Waters, B. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_5 · Cited by 1,492 · cited 3×
“LWE has been used extensively to construct applications such as Leveled Fully Homomorphic Encryption [41, 43, 71], Lockable Obfuscation [80, 114], Attribute Based Encryption [32, 78, 79] and Universal Thresholdizers [31].”
Self-citationEfficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449 · cited 2×
“LWE has been used extensively to construct applications such as Leveled Fully Homomorphic Encryption [41, 43, 71], Lockable Obfuscation [80, 114], Attribute Based Encryption [32, 78, 79] and Universal Thresholdizers [31].”
On the (Im)possibility of Obfuscating Programs
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., & Yang, K. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_1 · Cited by 1,286
Self-citationCandidate Indistinguishability Obfuscation and Functional Encryption for all Circuits
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., & Waters, B. R. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.13 · Cited by 1,277 · cited 1×
“In this work, we study the notion of indistinguishability obfuscation (iO) for general polynomial-size circuits [19, 66, 77].”
Self-citationEfficient Non-interactive Proof Systems for Bilinear Groups
Groth, J., & Sahai, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78967-3_24 · Cited by 1,076
Self-citationHow to use indistinguishability obfuscation: deniable encryption, and more
Sahai, A., & Waters, B. (2014) · Proceedings of the forty-sixth annual ACM symposium on Theory of computing · doi:10.1145/2591796.2591825 · Cited by 624
Self-citationA Comparison of Signalling Alphabets
Gilbert, E. N. (1952) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1952.tb01393.x · Cited by 522 · cited 2×
“The origins of the LPN assumption date all the way back to the 1950s: the works of Gilbert [74] and Varshamov [112] showed that random linear codes possessed remarkably strong minimum distance properties.”
Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption
Okamoto, T., & Takashima, K. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_11 · Cited by 507
Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits
Boneh, D., Gentry, C., Gorbunov, S., Halevi, S., Nikolaenko, V., Segev, G., Vaikuntanathan, V., & Vinayagamurthy, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-55220-5_30 · Cited by 492 · cited 3×
“LWE has been used extensively to construct applications such as Leveled Fully Homomorphic Encryption [41, 43, 71], Lockable Obfuscation [80, 114], Attribute Based Encryption [32, 78, 79] and Universal Thresholdizers [31].”
InfluentialSeparating succinct non-interactive arguments from all falsifiable assumptions
Gentry, C., & Wichs, D. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993651 · Cited by 456 · cited 1×
“2This construction does not contradict the lower bound result by [72] showing that it is impossible to base the adaptive soundness of SNARGs on falsifiable assumptions via black-box reductions, since this construction only achieves selective soundness.”
Attribute-based encryption for circuits
Gorbunov, S., Vaikuntanathan, V., & Wee, H. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488677 · Cited by 406
Multi-input Functional Encryption
Goldwasser, S., Gordon, S. D., Goyal, V., Jain, A., Katz, J., Liu, F.-H., Sahai, A., Shi, E., & Zhou, H.-S. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-55220-5_32 · Cited by 349
Self-citationCryptographic Primitives Based on Hard Learning Problems
Blum, A., Furst, M., Kearns, M., & Lipton, R. J. (1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_24 · Cited by 332 · cited 10×
“Indistinguishability Obfuscation from Well-Founded Assumptions.”
InfluentialCryptanalysis of the Multilinear Map over the Integers
Cheon, J. H., Han, K., Lee, C., Ryu, H., & Stehlé, D. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46800-5_1 · Cited by 291 · cited 1×
“Indeed, the process of understanding these assumptions has been tortuous, with several of these assumptions broken by clever cryptanalysis [18, 21, 33, 40, 53, 54, 60, 82, 85, 103, 105, 106].”
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85174-5_3 · Cited by 286 · cited 1×
“In this work, we study the notion of indistinguishability obfuscation (iO) for general polynomial-size circuits [19, 66, 77].”
More on average case vs approximation complexity
Alekhnovich, M. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238204 · Cited by 247
Fiat-Shamir: from practice to theory
Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G. N., Rothblum, R. D., & Wichs, D. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316380 · Cited by 247 · cited 1×
“Regarding PPAD hardness, another line of beautiful works [45, 55, 56, 64, 92, 104] showed that the hardness of #SAT reduces to that of PPAD, assuming the adaptive soundness of applying FiatShamir to certain protocols.”
Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage
Brakerski, Z., Kalai, Y. T., Katz, J., & Vaikuntanathan, V. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.55 · Cited by 242
Threshold Cryptosystems from Threshold Fully Homomorphic Encryption
Boneh, D., Gennaro, R., Goldfeder, S., Jain, A., Kim, S., Rasmussen, P. M. R., & Sahai, A. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-96884-1_19 · Cited by 238 · cited 2×
“LWE has been used extensively to construct applications such as Leveled Fully Homomorphic Encryption [41, 43, 71], Lockable Obfuscation [80, 114], Attribute Based Encryption [32, 78, 79] and Universal Thresholdizers [31].”
Self-citationPublic-key cryptography from different assumptions
Applebaum, B., Barak, B., & Wigderson, A. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806715 · Cited by 235 · cited 3×
“The complexity theory and cryptography communities have jointly developed a rich body of literature on the cryptanalysis and theory of constant-locality Boolean PRGs [9, 10, 12, 13, 15, 16,”
Predicate Encryption for Circuits from LWE
Gorbunov, S., Vaikuntanathan, V., & Wee, H. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-48000-7_25 · Cited by 217 · cited 3×
“LWE has been used extensively to construct applications such as Leveled Fully Homomorphic Encryption [41, 43, 71], Lockable Obfuscation [80, 114], Attribute Based Encryption [32, 78, 79] and Universal Thresholdizers [31].”
InfluentialEfficient Two-Round OT Extension and Silent Non-Interactive Secure Computation
Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Rindal, P., & Scholl, P. (2019) · Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3319535.3354255 · Cited by 200 · cited 2×
“This assumption has been used in a various works (see for example, [11, 14, 22, 35, 36, 63, 73, 88]).”
Boyle, E., Couteau, G., Gilboa, N., & Ishai, Y. (2018) · Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3243734.3243868 · Cited by 194 · cited 15×
“This assumption has been used in a various works (see for example, [11, 14, 22, 35, 36, 63, 73, 88]).”
InfluentialShorter Quasi-Adaptive NIZK Proofs for Linear Subspaces
Jutla, C. S., & Roy, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-42033-7_1 · Cited by 185
Function-Hiding Inner Product Encryption
Bishop, A., Jain, A., & Kowalczyk, L. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48797-6_20 · Cited by 176
Self-citationIndistinguishability Obfuscation for Turing Machines with Unbounded Memory
Koppula, V., Lewko, A. B., & Waters, B. R. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746614 · Cited by 160
Cryptography with constant computational overhead
Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374438 · Cited by 158 · cited 1×
“PRGs in NC0 are tightly connected to the fundamental topic of Constraint Satisfaction Problems (CSPs) in complexity theory, and were first proposed for cryptographic use by Goldreich [62, 75, 87] 20 years ago.”
Self-citationGoyal, R., Koppula, V., & Waters, B. R. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.62 · Cited by 157 · cited 2×
“LWE has been used extensively to construct applications such as Leveled Fully Homomorphic Encryption [41, 43, 71], Lockable Obfuscation [80, 114], Attribute Based Encryption [32, 78, 79] and Universal Thresholdizers [31].”
Obfuscation of Probabilistic Circuits and Applications
Canetti, R., Lin, H., Tessaro, S., & Vaikuntanathan, V. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46497-7_19 · Cited by 155
Self-citationSuccinct Randomized Encodings and their Applications
Bitansky, N., Garg, S., Lin, H., Pass, R., & Telang, S. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746574 · Cited by 152
Self-citationSecure Arithmetic Computation with No Honest Majority
Ishai, Y., Prabhakaran, M., & Sahai, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00457-5_18 · Cited by 145 · cited 13×
“This assumption has been used in a various works (see for example, [11, 14, 22, 35, 36, 63, 73, 88]).”
InfluentialSelf-citationOn the Cryptographic Hardness of Finding a Nash Equilibrium
Bitansky, N., Paneth, O., & Rosen, A. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.94 · Cited by 128
Correlated Pseudorandom Functions from Variable-Density LPN
Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., & Schöll, P. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00103 · Cited by 114 · cited 2×
“We refer the reader to [35, 37] for a comprehensive discussion of the history and security of this assumption.”
Continuous Verifiable Delay Functions
Ephraim, N., Freitag, C., Komargodski, I., & Pass, R. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45727-3_5 · Cited by 109 · cited 1×
“Regarding PPAD hardness, another line of beautiful works [45, 55, 56, 64, 92, 104] showed that the hardness of #SAT reduces to that of PPAD, assuming the adaptive soundness of applying FiatShamir to certain protocols.”
From Obfuscation to the Security of Fiat-Shamir for Proofs
Kalai, Y. T., Rothblum, G. N., & Rothblum, R. D. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63715-0_8 · Cited by 107
Secure Arithmetic Computation with Constant Computational Overhead
Applebaum, B., Damgård, I., Ishai, Y., Nielsen, M., & Zichron, L. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63688-7_8 · Cited by 100 · cited 2×
“This assumption has been used in a various works (see for example, [11, 14, 22, 35, 36, 63, 73, 88]).”
Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
Canetti, R., Holmgren, J., Jain, A., & Vaikuntanathan, V. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746621 · Cited by 98
Self-citationRevisiting the Cryptographic Hardness of Finding a Nash Equilibrium
Garg, S., Pandey, O., & Srinivasan, A. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53008-5_20 · Cited by 94 · cited 1×
“In comparison, relying on [67], using our Functional Encryption construction, we can base the PPAD hardness on the polynomial security of the four assumptions we make.”
On ε-biased generators in NC/sup 0/
Mossel, E., Shpilka, A., & Trevisan, L. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238188 · Cited by 91
Algebraic Attacks against Random Local Functions and Their Countermeasures
Applebaum, B., & Lovett, S. (2016) · SIAM Journal on Computing · doi:10.1137/16m1085942 · Cited by 90
Candidate iO from Homomorphic Encryption Schemes
Brakerski, Z., Döttling, N., Garg, S., & Malavolta, G. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45721-1_4 · Cited by 70
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
Choudhuri, A. R., Hubáček, P., Kamath, C., Pietrzak, K., Rosen, A., & Rothblum, G. N. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316400 · Cited by 65 · cited 1×
“Regarding PPAD hardness, another line of beautiful works [45, 55, 56, 64, 92, 104] showed that the hardness of #SAT reduces to that of PPAD, assuming the adaptive soundness of applying FiatShamir to certain protocols.”
TinyOLE: Efficient Actively Secure Two-Party Computation from Oblivious Linear Function Evaluation
Döttling, N., Ghosh, S., Nielsen, J. B., Nilges, T., & Trifiletti, R. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3134024 · Cited by 59 · cited 2×
“This assumption has been used in a various works (see for example, [11, 14, 22, 35, 36, 63, 73, 88]).”
On the Correlation Intractability of Obfuscated Pseudorandom Functions
Canetti, R., Chen, Y., & Reyzin, L. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-49096-9_17 · Cited by 59 · cited 1×
“circuits [47], or for all sparse relations, assuming additionally”
On the Security of Goldreich’s One-Way Function
Bogdanov, A., & Qiao, Y. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03685-9_30 · Cited by 49
Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs
Lombardi, A., & Vaikuntanathan, V. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-56877-1_22 · Cited by 49 · cited 1×
“Regarding PPAD hardness, another line of beautiful works [45, 55, 56, 64, 92, 104] showed that the hardness of #SAT reduces to that of PPAD, assuming the adaptive soundness of applying FiatShamir to certain protocols.”
Constant-Round Concurrent Zero-Knowledge from Indistinguishability Obfuscation
Chung, K.-M., Lin, H., & Pass, R. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47989-6_14 · Cited by 49
Self-citationMaliciously Secure Oblivious Linear Function Evaluation with Constant Overhead
Ghosh, S., Nielsen, J. B., & Nilges, T. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70694-8_22 · Cited by 46 · cited 2×
“This assumption has been used in a various works (see for example, [11, 14, 22, 35, 36, 63, 73, 88]).”
Komargodski, I., Naor, M., & Yogev, E. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45608-8_14 · Cited by 46
A Dichotomy for Local Small-Bias Generators
Applebaum, B., Bogdanov, A., & Rosen, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28914-9_34 · Cited by 41
Succinct Garbling Schemes from Functional Encryption Through a Local Simulation Paradigm
Ananth, P., & Lombardi, A. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-03810-6_17 · Cited by 41
On the security of Goldreich’s one-way function
Bogdanov, A., & Qiao, Y. (2012) · Computational Complexity · doi:10.1007/s00037-011-0034-0 · Cited by 36 · cited 2×
“The complexity theory and cryptography communities have jointly developed a rich body of literature on the cryptanalysis and theory of constant-locality Boolean PRGs [9, 10, 12, 13, 15, 16,”
Symmetric Primitives with Structured Secrets
Alamati, N., Montgomery, H. W., & Patranabis, S. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-26948-7_23 · Cited by 35 · cited 1×
“polynomial multilinear degrees, following [2, 3, 65], and self-”
Indistinguishability Obfuscation from Well-Founded Assumptions
Jain, A., Lin, H., & Sahai, A. (2025) · Journal of the ACM · doi:10.1145/3785007 · Cited by 28
Self-citationApplebaum, B., Avron, J., & Brzuska, C. (2015) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2688073.2688114 · Cited by 26 · cited 12×
“This assumption has been used in a various works (see for example, [11, 14, 22, 35, 36, 63, 73, 88]).”
Influential
Cited by
Planting Undetectable Backdoors in Machine Learning Models : [Extended Abstract]
Goldwasser, S., Kim, M. P., Vaikuntanathan, V., & Zamir, O. (2022) · 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) · doi:10.1109/focs54457.2022.00092 · Cited by 41
Metadata
- Authors
- Jain, A., Lin, H., & Sahai, A.
- Venue
- Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
- Publisher
- ACM
- Published
- 2021-06-15
- Pages
- 60-73
- OpenAlex
- W3082860856
- Cited by
- 237
- References
- 59
- FWCI
- 19.13
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.