{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T01:57:03Z","timestamp":1783562223014,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":64,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DARPA SIEVE","award":["HR00110C0086"],"award-info":[{"award-number":["HR00110C0086"]}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["SATC-1704788,RI-1703846"],"award-info":[{"award-number":["SATC-1704788,RI-1703846"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004332","name":"JPMorgan Chase and Company","doi-asserted-by":"publisher","award":["Faculty Award"],"award-info":[{"award-number":["Faculty Award"]}],"id":[{"id":"10.13039\/100004332","id-type":"DOI","asserted-by":"publisher"}]},{"name":"AFOSR","award":["FA9550-18-1-0267"],"award-info":[{"award-number":["FA9550-18-1-0267"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451070","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"736-749","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":67,"title":["Indistinguishability obfuscation from circular security"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3864-9756","authenticated-orcid":false,"given":"Romain","family":"Gay","sequence":"first","affiliation":[{"name":"IBM Research, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[{"name":"Cornell Tech, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Tolga Acar Mira Belenkiy Mihir Bellare and David Cash. 2010. Cryptographic Agility and Its Relation to Circular Encryption. 403\u2013422. 10.1007\/978-3-642-13190-5_21","DOI":"10.1007\/978-3-642-13190-5_21"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_7"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Mikl\u00f3s Ajtai. 1996. Generating Hard Instances of Lattice Problems (Extended Abstract). 99\u2013108. 10.1145\/237814.237838","DOI":"10.1145\/237814.237838"},{"key":"e_1_3_2_1_5_1","unstructured":"Jo\u00ebl Alwen and Chris Peikert. 2009. Generating Shorter Bases for Hard Random Lattices. In 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science) Susanne Albers and Jean-Yves Marion (Eds.). IBFI Schloss Dagstuhl Freiburg Germany 75\u201386."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","unstructured":"Prabhanjan Ananth and Abhishek Jain. 2015. Indistinguishability Obfuscation from Compact Functional Encryption. 308\u2013326. 10.1007\/978-3-662-47989-6_15","DOI":"10.1007\/978-3-662-47989-6_15"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Boaz Barak Oded Goldreich Russell Impagliazzo Steven Rudich Amit Sahai Salil P. Vadhan and Ke Yang. 2001. On the (Im)possibility of Obfuscating Programs. 1\u201318. 10.1007\/3-540-44647-8_1","DOI":"10.1007\/3-540-44647-8_1"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.82"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Allison Bishop Susan Hohenberger and Brent Waters. 2015. New Circular Security Counterexamples from Decision Linear and Learning with Errors. 776\u2013800. 10.1007\/978-3-662-48800-3_32","DOI":"10.1007\/978-3-662-48800-3_32"},{"key":"e_1_3_2_1_13_1","first-page":"356","article-title":"Succinct Randomized Encodings and their Applications","volume":"2015","author":"Bitansky Nir","year":"2015","unstructured":"Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang. 2015. Succinct Randomized Encodings and their Applications. IACR Cryptology ePrint Archive 2015 (2015), 356. http:\/\/eprint.iacr.org\/2015\/356","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Nir Bitansky and Omer Paneth. 2015. ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation. 401\u2013427. 10.1007\/978-3-662-46497-7_16","DOI":"10.1007\/978-3-662-46497-7_16"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Nir Bitansky Omer Paneth and Alon Rosen. 2015. On the Cryptographic Hardness of Finding a Nash Equilibrium. 1480\u20131498. 10.1109\/FOCS.2015.94","DOI":"10.1109\/FOCS.2015.94"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Nir Bitansky Omer Paneth and Daniel Wichs. 2016. Perfect Structure on the Edge of Chaos - Trapdoor Permutations from Indistinguishability Obfuscation. 474\u2013502. 10.1007\/978-3-662-49096-9_20","DOI":"10.1007\/978-3-662-49096-9_20"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Nir Bitansky and Vinod Vaikuntanathan. 2015. Indistinguishability Obfuscation from Functional Encryption. 171\u2013190. 10.1109\/FOCS.2015.20","DOI":"10.1109\/FOCS.2015.20"},{"key":"e_1_3_2_1_18_1","unstructured":"J. Black P. Rogaway and T. Shrimpton. 2002. Encryption-Scheme Security in the Presence of Key-Dependent Messages. Cryptology ePrint Archive Report 2002\/100. https:\/\/eprint.iacr.org\/2002\/100."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44371-2_27"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Elette Boyle Kai-Min Chung and Rafael Pass. 2014. On Extractability Obfuscation. In TCC. 52\u201373.","DOI":"10.1007\/978-3-642-54242-8_3"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Zvika Brakerski Nico D\u00f6ttling Sanjam Garg and Giulio Malavolta. 2019. Leveraging Linear Decryption: Rate-1 Fully-Homomorphic Encryption and Time-Lock Puzzles. 407\u2013437. 10.1007\/978-3-030-36033-7_16","DOI":"10.1007\/978-3-030-36033-7_16"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Zvika Brakerski Nico D\u00f6ttling Sanjam Garg and Giulio Malavolta. 2020. Candidate iO from Homomorphic Encryption Schemes. 79\u2013109. 10.1007\/978-3-030-45721-1_4","DOI":"10.1007\/978-3-030-45721-1_4"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Jan Camenisch and Anna Lysyanskaya. 2001. An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. 93\u2013118. 10.1007\/3-540-44987-6_7","DOI":"10.1007\/3-540-44987-6_7"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276741"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46497-7_18"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","unstructured":"David Cash Matthew Green and Susan Hohenberger. 2012. New Definitions and Separations for Circular Security. 540\u2013557. 10.1007\/978-3-642-30057-8_32","DOI":"10.1007\/978-3-642-30057-8_32"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46800-5_1"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Kai-Min Chung Huijia Lin and Rafael Pass. 2015. Constant-Round Concurrent Zero-Knowledge from Indistinguishability Obfuscation. 287\u2013307. 10.1007\/978-3-662-47989-6_14","DOI":"10.1007\/978-3-662-47989-6_14"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_26"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47989-6_13"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Ivan Damg\\aard and Mats Jurik. 2001. A Generalisation a Simplification and Some Applications of Paillier's Probabilistic Public-Key System. 119\u2013136. 10.1007\/3-540-44586-2_9","DOI":"10.1007\/3-540-44586-2_9"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Sanjam Garg Craig Gentry and Shai Halevi. 2013. Candidate Multilinear Maps from Ideal Lattices. 1\u201317. 10.1007\/978-3-642-38348-9_1","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54242-8_4"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","unstructured":"Sanjam Garg Craig Gentry Shai Halevi Mariana Raykova Amit Sahai and Brent Waters. 2013. Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits. 40\u201349. 10.1109\/FOCS.2013.13","DOI":"10.1109\/FOCS.2013.13"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. 169\u2013178. 10.1145\/1536414.1536440","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Craig Gentry Sergey Gorbunov and Shai Halevi. 2015. Graph-Induced Multilinear Maps from Lattices. 498\u2013527. 10.1007\/978-3-662-46497-7_20","DOI":"10.1007\/978-3-662-46497-7_20"},{"key":"e_1_3_2_1_40_1","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.. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 25. 149.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","unstructured":"Craig Gentry Chris Peikert and Vinod Vaikuntanathan. 2008. Trapdoors for hard lattices and new cryptographic constructions. 197\u2013206. 10.1145\/1374376.1374407","DOI":"10.1145\/1374376.1374407"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.60"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","unstructured":"Rishab Goyal Venkata Koppula and Brent Waters. 2017. Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption. 528\u2013557. 10.1007\/978-3-319-56614-6_18","DOI":"10.1007\/978-3-319-56614-6_18"},{"key":"e_1_3_2_1_46_1","unstructured":"Matthew Green and Susan Hohenberger. 2010. CPA and CCA-Secure Encryption Systems that are not 2-Circular Secure. http:\/\/eprint.iacr.org\/2010\/144 matthewdgreen@gmail.com 14686 received 16 Mar 2010 last revised 18 Mar 2010."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","unstructured":"Aayush Jain Huijia Lin Christian Matt and Amit Sahai. 2019. How to Leverage Hardness of Constant-Degree Expanding Polynomials overa $\\mathbbR$ to build $i\\mathcalO$. 251\u2013281. 10.1007\/978-3-030-17653-2_9","DOI":"10.1007\/978-3-030-17653-2_9"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","unstructured":"Ilan Komargodski Tal Moran Moni Naor Rafael Pass Alon Rosen and Eylon Yogev. 2014. One-Way Functions and (Im)Perfect Obfuscation. 374\u2013383. 10.1109\/FOCS.2014.47","DOI":"10.1109\/FOCS.2014.47"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","unstructured":"Ilan Komargodski Moni Naor and Eylon Yogev. 2014. Secret-Sharing for NP. 254\u2013273. 10.1007\/978-3-662-45608-8_14","DOI":"10.1007\/978-3-662-45608-8_14"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746614"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","unstructured":"Venkata Koppula Kim Ramchen and Brent Waters. 2015. Separations in Circular Security for Arbitrary Length Key Cycles. 378\u2013400. 10.1007\/978-3-662-46497-7_15","DOI":"10.1007\/978-3-662-46497-7_15"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","unstructured":"Venkata Koppula and Brent Waters. 2016. Circular Security Separations for Arbitrary Length Cycles from LWE. 681\u2013700. 10.1007\/978-3-662-53008-5_24","DOI":"10.1007\/978-3-662-53008-5_24"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","unstructured":"Huijia Lin. 2016. Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes. 28\u201357. 10.1007\/978-3-662-49890-3_2","DOI":"10.1007\/978-3-662-49890-3_2"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","unstructured":"Huijia Lin. 2017. Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs. 599\u2013629. 10.1007\/978-3-319-63688-7_20","DOI":"10.1007\/978-3-319-63688-7_20"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","unstructured":"Huijia Lin Rafael Pass Karn Seth and Sidharth Telang. 2016. Indistinguishability Obfuscation with Non-trivial Efficiency. 447\u2013462. 10.1007\/978-3-662-49387-8_17","DOI":"10.1007\/978-3-662-49387-8_17"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","unstructured":"Huijia Lin and Stefano Tessaro. 2017. Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs. 630\u2013660. 10.1007\/978-3-319-63688-7_21","DOI":"10.1007\/978-3-319-63688-7_21"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","unstructured":"Huijia Lin and Vinod Vaikuntanathan. 2016. Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings. 11\u201320. 10.1109\/FOCS.2016.11","DOI":"10.1109\/FOCS.2016.11"},{"key":"e_1_3_2_1_60_1","first-page":"632","article-title":"More on Impossibility of Virtual Black-Box Obfuscation in Idealized Models","volume":"2015","author":"Mahmoody Mohammad","year":"2015","unstructured":"Mohammad Mahmoody, Ameer Mohammed, and Soheil Nematihaji. 2015. More on Impossibility of Virtual Black-Box Obfuscation in Idealized Models. IACR Cryptology ePrint Archive 2015 (2015), 632. http:\/\/eprint.iacr.org\/2015\/632","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","unstructured":"Antonio Marcedone and Claudio Orlandi. 2014. Obfuscation $\\Rightarrow$ (IND-CPA Security $\\not\\Rightarrow$ Circular Security). 77\u201390. 10.1007\/978-3-319-10879-7_5","DOI":"10.1007\/978-3-319-10879-7_5"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","unstructured":"Ueli M. Maurer Renato Renner and Clemens Holenstein. 2004. Indifferentiability Impossibility Results on Reductions and Applications to the Random Oracle Methodology. 21\u201339. 10.1007\/978-3-540-24638-1_2","DOI":"10.1007\/978-3-540-24638-1_2"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","unstructured":"Rafael Pass Karn Seth and Sidharth Telang. 2014. Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings. 500\u2013517. 10.1007\/978-3-662-44371-2_28","DOI":"10.1007\/978-3-662-44371-2_28"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","unstructured":"Rafael Pass and abhi shelat. 2016. Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings. 3\u201317. 10.1007\/978-3-662-49096-9_1","DOI":"10.1007\/978-3-662-49096-9_1"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","unstructured":"Chris Peikert Oded Regev and Noah Stephens-Davidowitz. 2017. Pseudorandomness of ring-LWE for any ring and modulus. 461\u2013473. 10.1145\/3055399.3055489","DOI":"10.1145\/3055399.3055489"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","unstructured":"Chris Peikert Vinod Vaikuntanathan and Brent Waters. 2008. A Framework for Efficient and Composable Oblivious Transfer. 554\u2013571. 10.1007\/978-3-540-85174-5_31","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","unstructured":"Oded Regev. 2005. On lattices learning with errors random linear codes and cryptography. 84\u201393. 10.1145\/1060590.1060603","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","unstructured":"Ron Rothblum. 2013. On the Circular Security of Bit-Encryption. 579\u2013598. 10.1007\/978-3-642-36594-2_32","DOI":"10.1007\/978-3-642-36594-2_32"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","unstructured":"Amit Sahai and Brent Waters. 2014. How to use indistinguishability obfuscation: deniable encryption and more. 475\u2013484. 10.1145\/2591796.2591825","DOI":"10.1145\/2591796.2591825"},{"key":"e_1_3_2_1_73_1","unstructured":"Huijia Lin Samuel B. Hopkins Aayush Jain. 2021. Counterexamples to New Circular Security Assumptions Underlying iO. (2021). manuscript."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","unstructured":"Daniel Wichs and Giorgos Zirdelis. 2017. Obfuscating Compute-and-Compare Programs under LWE. 600\u2013611. 10.1109\/FOCS.2017.61","DOI":"10.1109\/FOCS.2017.61"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451070","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451070","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451070","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451070"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":64,"alternative-id":["10.1145\/3406325.3451070","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451070","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}