{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T16:19:13Z","timestamp":1770913153886,"version":"3.50.1"},"reference-count":158,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T00:00:00Z","timestamp":1770854400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CNS-1528178, CNS-1929901, CNS-1936825\u00a0(CAREER), CNS-2026774"],"award-info":[{"award-number":["CNS-1528178, CNS-1929901, CNS-1936825\u00a0(CAREER), CNS-2026774"]}]},{"name":"Hellman Fellowship, a JP Morgan AI research Award, a Simons collaboration grant on algorithmic fairness, the Defense Advanced Research Projects Agency (DARPA) and Army Research Office","award":["W911NF-15-C-0236"],"award-info":[{"award-number":["W911NF-15-C-0236"]}]},{"name":"DARPA SAFEWARE and SIEVE awards, NTT Research, NSF Frontier Award","award":["1413955"],"award-info":[{"award-number":["1413955"]}]},{"name":"NSF","award":["1619348, 2333935"],"award-info":[{"award-number":["1619348, 2333935"]}]},{"name":"BSF","award":["2012378"],"award-info":[{"award-number":["2012378"]}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"crossref","award":["HR00112020024"],"award-info":[{"award-number":["HR00112020024"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ARL","award":["W911NF-15-C- 0205"],"award-info":[{"award-number":["W911NF-15-C- 0205"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,2,28]]},"abstract":"Indistinguishability obfuscation, introduced by [Barak et. al. Crypto\u20192001], 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.<\/jats:p>\n In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove:<\/jats:p>\n \n Suppose there exists any set of constants\n \n \\(\\tau \\in (0,\\infty), \\delta \\in (0,1), \\epsilon \\in (0,1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that the sub-exponential security of the following assumptions hold:\n \n \n \u2014<\/jats:label>\n \n the Learning With Errors (\n \n \\(\\mathsf {LWE}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) assumption with subexponential modulus-to-noise ratio\n \n \\(2^{k^\\epsilon }\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and noises of magnitude polynomial in\n k<\/jats:italic>\n , where\n k<\/jats:italic>\n is the dimension of the\n \n \\(\\mathsf {LWE}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n secret,\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n the Learning Parity with Noise (\n \n \\(\\mathsf {LPN}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) assumption over general prime fields\n \n \\(\\mathbb {Z}_p\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n with polynomially many\n \n \\(\\mathsf {LPN}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n samples and error rate\n \n \\(1\/\\ell ^\\delta\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the dimension of the\n \n \\(\\mathsf {LPN}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n secret,\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n the existence of a Boolean Pseudo-Random Generator (\n \n \\(\\mathsf {PRG}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) in\n \n \\(\\mathsf {NC}^0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n with stretch\n \n \\(n^{1+\\tau }\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n n<\/jats:italic>\n is the length of the\n \n \\(\\mathsf {PRG}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n seed,\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n the Decision Linear (\n \n \\(\\mathsf {DLIN}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ) assumption on symmetric bilinear groups of prime order.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>\n Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.<\/jats:p>\n Furthermore, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits.<\/jats:p>","DOI":"10.1145\/3785007","type":"journal-article","created":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T12:12:48Z","timestamp":1765541568000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Indistinguishability Obfuscation from Well-Founded Assumptions"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-7138-2777","authenticated-orcid":false,"given":"Aayush","family":"Jain","sequence":"first","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University","place":["Pittsburgh, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2206-4817","authenticated-orcid":false,"given":"Huijia","family":"Lin","sequence":"additional","affiliation":[{"name":"Computer Science, University of Washington","place":["Seattle, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2216-9600","authenticated-orcid":false,"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[{"name":"Center of Encrypted Functionalities, Computer Science Department, University of California Los Angeles","place":["Los Angeles, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,12]]},"reference":[{"key":"e_1_3_3_2_2","article-title":"On algorithms for nash equilibria","author":"Abbot Tim","year":"2004","unstructured":"Tim Abbot, Daniel Kane, and Paul Valiant. 2004. On algorithms for nash equilibria. unpublished manuscript. (2004). Retrieved from https:\/\/web.mit.edu\/tabbott\/Public\/final.pdf","journal-title":"unpublished manuscript"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_7"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_5"},{"key":"e_1_3_3_5_2","article-title":"Symmetric Primitives with Structured Secrets","author":"Alamati Navid","year":"2019","unstructured":"Navid Alamati, Hart Montgomery, and Sikhar Patranabis. 2019. Symmetric Primitives with Structured Secrets. Cryptology ePrint Archive, Report 2019\/608. (2019). Retrieved from https:\/\/eprint.iacr.org\/2019\/608","journal-title":"Cryptology ePrint Archive, Report 2019\/608"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49096-9_19"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_1"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660342"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47989-6_15"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_10"},{"key":"e_1_3_3_12_2","first-page":"2015","article-title":"Indistinguishability obfuscation from functional encryption for simple functions","volume":"730","author":"Ananth Prabhanjan","year":"2015","unstructured":"Prabhanjan Ananth, Abhishek Jain, and Amit Sahai. 2015. Indistinguishability obfuscation from functional encryption for simple functions. Eprint 730 (2015), 2015. https:\/\/eprint.iacr.org\/2015\/730","journal-title":"Eprint"},{"key":"e_1_3_3_13_2","first-page":"615","article-title":"Indistinguishability obfuscation without multilinear maps: iO from LWE, bilinear maps, and weak pseudorandomness","volume":"2018","author":"Ananth Prabhanjan","year":"2018","unstructured":"Prabhanjan Ananth, Aayush Jain, and Amit Sahai. 2018. Indistinguishability obfuscation without multilinear maps: iO from LWE, bilinear maps, and weak pseudorandomness. IACR Cryptology ePrint Archive 2018 (2018), 615.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03810-6_17"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56620-7_6"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214050"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/120884857"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688114"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806714"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_34"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63688-7_8"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00020"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897554"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_27"},{"key":"e_1_3_3_25_2","first-page":"60","article-title":"Limits on low-degree pseudorandom generators (Or: Sum-of-squares meets program obfuscation)","volume":"24","author":"Barak Boaz","year":"2017","unstructured":"Boaz Barak, Zvika Brakerski, Ilan Komargodski, and Pravesh Kothari. 2017. Limits on low-degree pseudorandom generators (Or: Sum-of-squares meets program obfuscation). Electronic Colloquium on Computational Complexity (ECCC) 24 (2017), 60.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_13"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44647-8_1"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44647-8_1"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_8"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.82"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17659-4_22"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48797-6_20"},{"key":"e_1_3_3_33_2","first-page":"463","article-title":"In pursuit of clarity in obfuscation","volume":"2019","author":"Bishop Allison","year":"2019","unstructured":"Allison Bishop, Lucas Kowalczyk, Tal Malkin, Valerio Pastro, Mariana Raykova, and Kevin Shi. 2019. In pursuit of clarity in obfuscation. IACR Cryptol. ePrint Arch. 2019 (2019), 463. Retrieved from https:\/\/eprint.iacr.org\/2019\/463","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746574"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.94"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.20"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48329-2_24"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_30"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0034-0"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28628-8_3"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_19"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_30"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_23"},{"key":"e_1_3_3_44_2","article-title":"Immunizing Multilinear Maps Against Zeroizing Attacks","author":"Boneh Dan","year":"2014","unstructured":"Dan Boneh, David J. Wu, and Joe Zimmerman. 2014. Immunizing Multilinear Maps Against Zeroizing Attacks. Cryptology ePrint Archive, Report 2014\/930. (2014).","journal-title":"Cryptology ePrint Archive, Report 2014\/930"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44371-2_27"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243868"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354255"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00103"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_4"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_4"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","unstructured":"Zvika Brakerski Nico D\u00f6ttling Sanjam Garg and Giulio Malavolta. 2022. Factoring and pairings are not necessary for IO: Circular-secure LWE suffices(LIPIcs). Schloss Dagstuhl 28:1\u201328:20. DOI:DOI:10.4230\/LIPIcs.ICALP.2022.28","DOI":"10.4230\/LIPIcs.ICALP.2022.28"},{"key":"e_1_3_3_52_2","article-title":"Cryptanalysis of the Quadratic Zero-Testing of GGH","author":"Brakerski Zvika","year":"2015","unstructured":"Zvika Brakerski, Craig Gentry, Shai Halevi, Tancrede Lepoint, Amit Sahai, and Mehdi Tibouchi. 2015. Cryptanalysis of the Quadratic Zero-Testing of GGH. Cryptology ePrint Archive, Report 2015\/845. (2015). Retrieved from http:\/\/eprint.iacr.org\/","journal-title":"Cryptology ePrint Archive, Report 2015\/845"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090262"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.55"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488680"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54242-8_1"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46497-7_1"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44371-2_11"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316380"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_3"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49096-9_17"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840765"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746621"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46497-7_19"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56784-2_27"},{"key":"e_1_3_3_67_2","article-title":"Cryptography for Parallel RAM from Indistinguishability Obfuscation","author":"Chen Yu-Chi","year":"2015","unstructured":"Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, and Hong-Sheng Zhou. 2015. Cryptography for Parallel RAM from Indistinguishability Obfuscation. Cryptology ePrint Archive, Report 2015\/406. (2015). Retrieved from https:\/\/eprint.iacr.org\/2015\/406","journal-title":"Cryptology ePrint Archive, Report 2015\/406"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46800-5_1"},{"key":"e_1_3_3_69_2","article-title":"Cryptanalysis of the New CLT Multilinear Maps","author":"Cheon Jung Hee","year":"2015","unstructured":"Jung Hee Cheon, Changmin Lee, and Hansol Ryu. 2015. Cryptanalysis of the New CLT Multilinear Maps. Cryptology ePrint Archive, Report 2015\/934. (2015). Retrieved from http:\/\/eprint.iacr.org\/","journal-title":"Cryptology ePrint Archive, Report 2015\/934"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316400"},{"key":"e_1_3_3_71_2","article-title":"PPAD-Hardness via Iterated Squaring Modulo a Composite","author":"Choudhuri Arka Rai","year":"2019","unstructured":"Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. 2019. PPAD-Hardness via Iterated Squaring Modulo a Composite. Cryptology ePrint Archive, Report 2019\/667. (2019). Retrieved from https:\/\/eprint.iacr.org\/2019\/667","journal-title":"Cryptology ePrint Archive, Report 2019\/667"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47989-6_14"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897651"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_31"},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47989-6_12"},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_26"},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47989-6_13"},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03329-3_4"},{"key":"e_1_3_3_79_2","first-page":"272","volume-title":"Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings (Lecture Notes in Computer Science)","volume":"2136","author":"Cryan Mary","year":"2001","unstructured":"Mary Cryan and Peter Bro Miltersen. 2001. On pseudorandom generators in NC. In Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings (Lecture Notes in Computer Science), Jiri Sgall, Ales Pultr, and Petr Kolman (Eds.). Vol. 2136. Springer, 272\u2013284."},{"key":"e_1_3_3_80_2","doi-asserted-by":"publisher","unstructured":"Lalita Devadas Willy Quach Vinod Vaikuntanathan Hoeteck Wee and Daniel Wichs. 2021. Succinct LWE sampling random polynomials and obfuscation(LNCS). Springer 256\u2013287. DOI:DOI:10.1007\/978-3-030-90453-1_9","DOI":"10.1007\/978-3-030-90453-1_9"},{"key":"e_1_3_3_81_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_4"},{"key":"e_1_3_3_82_2","first-page":"599","article-title":"Obfuscation from low noise multilinear maps","volume":"2016","author":"D\u00f6ttling Nico","year":"2016","unstructured":"Nico D\u00f6ttling, Sanjam Garg, Divya Gupta, Peihan Miao, and Pratyay Mukherjee. 2016. Obfuscation from low noise multilinear maps. IACR Cryptology ePrint Archive 2016 (2016), 599.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134024"},{"key":"e_1_3_3_84_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45727-3_5"},{"key":"e_1_3_3_85_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-76581-5_13"},{"key":"e_1_3_3_86_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"e_1_3_3_87_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.13"},{"key":"e_1_3_3_88_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5_20"},{"key":"e_1_3_3_89_2","first-page":"764","article-title":"Indistinguishability obfuscation from simple-to-state hard problems: New assumptions, new techniques, and simplification","volume":"2020","author":"Gay Romain","year":"2020","unstructured":"Romain Gay, Aayush Jain, Huijia Lin, and Amit Sahai. 2020. Indistinguishability obfuscation from simple-to-state hard problems: New assumptions, new techniques, and simplification. IACR Cryptol. ePrint Arch. 2020 (2020), 764.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_3_90_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77883-5_4"},{"key":"e_1_3_3_91_2","doi-asserted-by":"publisher","unstructured":"Romain Gay and Rafael Pass. 2021. Indistinguishability obfuscation from circular security. ACM Press 736\u2013749. DOI:DOI:10.1145\/3406325.3451070","DOI":"10.1145\/3406325.3451070"},{"key":"e_1_3_3_92_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46497-7_20"},{"key":"e_1_3_3_93_2","first-page":"149","article-title":"Obfuscation using tensor products","volume":"25","author":"Gentry Craig","year":"2018","unstructured":"Craig Gentry, Charanjit S. Jutla, and Daniel Kane. 2018. Obfuscation using tensor products. Electronic Colloquium on Computational Complexity (ECCC) 25 (2018), 149.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_3_94_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374407"},{"key":"e_1_3_3_95_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"e_1_3_3_96_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993651"},{"key":"e_1_3_3_97_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70694-8_22"},{"key":"e_1_3_3_98_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1952.tb01393.x"},{"issue":"90","key":"e_1_3_3_99_2","article-title":"Candidate one-way functions based on expander graphs","volume":"7","author":"Goldreich Oded","year":"2000","unstructured":"Oded Goldreich. 2000. Candidate one-way functions based on expander graphs. Electronic Colloquium on Computational Complexity (ECCC) 7, 90 (2000). Retrieved from https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2000\/TR00-090\/index.html","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_3_100_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_32"},{"key":"e_1_3_3_101_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_3"},{"key":"e_1_3_3_102_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488677"},{"key":"e_1_3_3_103_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_25"},{"key":"e_1_3_3_104_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.62"},{"key":"e_1_3_3_105_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78967-3_24"},{"key":"e_1_3_3_106_2","first-page":"866","article-title":"Graded encoding, variations on a scheme","volume":"2015","author":"Halevi Shai","year":"2015","unstructured":"Shai Halevi. 2015. Graded encoding, variations on a scheme. IACR Cryptology ePrint Archive 2015 (2015), 866.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_107_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53890-6_24"},{"key":"e_1_3_3_108_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_27"},{"key":"e_1_3_3_109_2","doi-asserted-by":"publisher","unstructured":"Samuel B. Hopkins Aayush Jain and Huijia Lin. 2021. Counterexamples to new circular security assumptions underlying iO(LNCS). Springer 673\u2013700. DOI:DOI:10.1007\/978-3-030-84245-1_23","DOI":"10.1007\/978-3-030-84245-1_23"},{"key":"e_1_3_3_110_2","first-page":"301","article-title":"Cryptanalysis of GGH map","volume":"2015","author":"Hu Yupu","year":"2015","unstructured":"Yupu Hu and Huiwen Jia. 2015. Cryptanalysis of GGH map. IACR Cryptology ePrint Archive 2015 (2015), 301.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_111_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.88"},{"key":"e_1_3_3_112_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374438"},{"key":"e_1_3_3_113_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_18"},{"key":"e_1_3_3_114_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30545-0_8"},{"key":"e_1_3_3_115_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_9"},{"key":"e_1_3_3_116_2","first-page":"1252","article-title":"Simplifying constructions and assumptions for \\(i\\mathcal {O}\\)","volume":"2019","author":"Jain Aayush","year":"2019","unstructured":"Aayush Jain, Huijia Lin, and Amit Sahai. 2019. Simplifying constructions and assumptions for \\(i\\mathcal {O}\\) . IACR Cryptol. ePrint Arch. 2019 (2019), 1252. Retrieved from https:\/\/eprint.iacr.org\/2019\/1252","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_3_117_2","doi-asserted-by":"publisher","unstructured":"Aayush Jain Huijia Lin and Amit Sahai. 2021. Indistinguishability obfuscation from well-founded assumptions. ACM Press 60\u201373. DOI:DOI:10.1145\/3406325.3451093","DOI":"10.1145\/3406325.3451093"},{"key":"e_1_3_3_118_2","doi-asserted-by":"publisher","unstructured":"Aayush Jain Huijia Lin and Amit Sahai. 2022. Indistinguishability obfuscation from LPN over \\(\\mathbb {F}_p\\) DLIN and PRGs in \\({NC}^0\\) (LNCS). Springer 670\u2013699. DOI:DOI:10.1007\/978-3-031-06944-4_23","DOI":"10.1007\/978-3-031-06944-4_23"},{"key":"e_1_3_3_119_2","article-title":"SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE","author":"Jawale Ruta","year":"2020","unstructured":"Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang. 2020. SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE. Cryptology ePrint Archive, Report 2020\/980. (2020). Retrieved from https:\/\/eprint.iacr.org\/2020\/980","journal-title":"Cryptology ePrint Archive, Report 2020\/980"},{"key":"e_1_3_3_120_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-42033-7_1"},{"key":"e_1_3_3_121_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63715-0_8"},{"key":"e_1_3_3_122_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48797-6_3"},{"key":"e_1_3_3_123_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.47"},{"key":"e_1_3_3_124_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45608-8_14"},{"key":"e_1_3_3_125_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56620-7_5"},{"key":"e_1_3_3_126_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746614"},{"key":"e_1_3_3_127_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746614"},{"key":"e_1_3_3_128_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_3_129_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49890-3_2"},{"key":"e_1_3_3_130_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63688-7_20"},{"key":"e_1_3_3_131_2","first-page":"646","article-title":"Pseudo flawed-smudging generators and their application to indistinguishability obfuscation","volume":"2018","author":"Lin Huijia","year":"2018","unstructured":"Huijia Lin and Christian Matt. 2018. Pseudo flawed-smudging generators and their application to indistinguishability obfuscation. IACR Cryptology ePrint Archive 2018 (2018), 646.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_132_2","article-title":"Pseudo Flawed-Smudging Generators and Their Application to Indistinguishability Obfuscation","author":"Lin Huijia","year":"2018","unstructured":"Huijia Lin and Christian Matt. 2018. Pseudo Flawed-Smudging Generators and Their Application to Indistinguishability Obfuscation. Cryptology ePrint Archive, Report 2018\/646. (2018). Retrieved from https:\/\/eprint.iacr.org\/2018\/646","journal-title":"Cryptology ePrint Archive, Report 2018\/646"},{"key":"e_1_3_3_133_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63688-7_21"},{"key":"e_1_3_3_134_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.11"},{"key":"e_1_3_3_135_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70500-2_5"},{"key":"e_1_3_3_136_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56877-1_22"},{"key":"e_1_3_3_137_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68403-6_2"},{"key":"e_1_3_3_138_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22792-9_26"},{"key":"e_1_3_3_139_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_2"},{"key":"e_1_3_3_140_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.72"},{"key":"e_1_3_3_141_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5_22"},{"key":"e_1_3_3_142_2","article-title":"Cryptanalysis of the New Multilinear Map over the Integers","author":"Minaud Brice","year":"2015","unstructured":"Brice Minaud and Pierre-Alain Fouque. 2015. Cryptanalysis of the New Multilinear Map over the Integers. Cryptology ePrint Archive, Report 2015\/941. (2015). Retrieved from http:\/\/eprint.iacr.org\/","journal-title":"Cryptology ePrint Archive, Report 2015\/941"},{"key":"e_1_3_3_143_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238188"},{"key":"e_1_3_3_144_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_26"},{"key":"e_1_3_3_145_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.9"},{"key":"e_1_3_3_146_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14623-7_11"},{"key":"e_1_3_3_147_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44371-2_28"},{"key":"e_1_3_3_148_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536461"},{"key":"e_1_3_3_149_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_3_3_150_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591825"},{"key":"e_1_3_3_151_2","article-title":"CS 294 Lecture 4: Worst-Case to Average-case Reductions for LWE","author":"Vaikunthananthan Vinod","year":"2020","unstructured":"Vinod Vaikunthananthan. 2020. CS 294 Lecture 4: Worst-Case to Average-case Reductions for LWE. Class at UC Berkeley. (2020). Retrieved from http:\/\/people.csail.mit.edu\/vinodv\/CS294\/lecture4.pdf","journal-title":"Class at UC Berkeley"},{"key":"e_1_3_3_152_2","article-title":"Estimate of the number of signals in error correcting codes","author":"Varshamov Rom","year":"1957","unstructured":"Rom Varshamov. 1957. Estimate of the number of signals in error correcting codes. Dokl. Akad. Nauk SSSR (1957).","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_3_3_153_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649671"},{"key":"e_1_3_3_154_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-032-01907-3_10"},{"key":"e_1_3_3_155_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68403-6_3"},{"key":"e_1_3_3_156_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64375-1_8"},{"key":"e_1_3_3_157_2","doi-asserted-by":"publisher","unstructured":"Hoeteck Wee and Daniel Wichs. 2021. Candidate obfuscation via oblivious LWE sampling(LNCS). Springer 127\u2013156. DOI:DOI:10.1007\/978-3-030-77883-5_5","DOI":"10.1007\/978-3-030-77883-5_5"},{"key":"e_1_3_3_158_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.61"},{"key":"e_1_3_3_159_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44381-1_6"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3785007","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3785007","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T15:29:14Z","timestamp":1770910154000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3785007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,12]]},"references-count":158,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2,28]]}},"alternative-id":["10.1145\/3785007"],"URL":"https:\/\/doi.org\/10.1145\/3785007","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,12]]},"assertion":[{"value":"2025-01-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}