{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:31:02Z","timestamp":1787340662281,"version":"build-2736575974"},"reference-count":74,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"JP Morgan"},{"DOI":"10.13039\/100004351","name":"Cisco Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004351","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1936825"],"award-info":[{"award-number":["CNS-1936825"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-2026774"],"award-info":[{"award-number":["CNS-2026774"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [C. Gentry, STOC \u201909, ACM, New York, 2009, pp. 169\u2013178; Z. Brakerski and V. Vaikuntanathan, FOCS \u201911, IEEE Computer Society, Los Alamitos, CA, 2011, pp. 97\u2013106], there is still a significant gap in understanding related homomorphic primitives supporting all unrestricted polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [S. Gorbunov, V. Vaikuntanathan, and H. Wee, STOC \u201913, ACM, New York, 2013, pp. 545\u2013554; D. Boneh et\u00a0al., Eurocrypt \u201914, Springer, Berlin, 2014, pp. 533\u2013556], only accommodate circuits up to a predetermined depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. An interesting question that has remained open for over a decade is whether the circular security assumptions enabling FHE can similarly benefit ABE. In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations: relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size; based on the evasive circular LWE assumption, a stronger variant of the recently proposed evasive LWE assumption [H. Wee, Eurocrypt \u201922, Springer, Cham, Switzerland, 2022, pp. 217\u2013241; R. Tsabary, Crypto \u201922, Springer, Cham, Switzerland, 2022, pp. 535\u2013559], we construct full-fledged ABE and predicate encryption (PE) schemes for circuits of unbounded depth and size. Our LFE, 1-key FE, and reusable garbling schemes achieve almost optimal succinctness (up to polynomial factors in the security parameter). Their ciphertexts and input encodings have sizes linear in the input length, while function digest, secret keys, and garbled circuits have constant sizes independent of circuit parameters (for Boolean outputs). In fact, this gives the first constant-size garbled circuits without relying on indistinguishability obfuscation. Our ABE and PE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant size.<\/jats:p>","DOI":"10.1137\/24m1629316","type":"journal-article","created":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T04:07:00Z","timestamp":1744862820000},"page":"FOCS23-90-FOCS23-146","source":"Crossref","is-referenced-by-count":0,"title":["Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More"],"prefix":"10.1137","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5244-7222","authenticated-orcid":true,"given":"Yao-Ching","family":"Hsieh","sequence":"first","affiliation":[{"name":"Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, WA 98195 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2206-4817","authenticated-orcid":true,"given":"Huijia","family":"Lin","sequence":"additional","affiliation":[{"name":"Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, WA 98195 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1225-5310","authenticated-orcid":true,"given":"Ji","family":"Luo","sequence":"additional","affiliation":[{"name":"Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, WA 98195 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,4,17]]},"reference":[{"key":"ref1","unstructured":"D. Abram, L. Roy, and M. Simkin, Time-Based Cryptography from Weaker Assumptions: Randomness Beacons, Delay Functions and More, Cryptology ePrint Archive, Report 2024\/769, https:\/\/eprint.iacr.org\/2024\/769 (2024)."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68382-4_11"},{"key":"ref3","unstructured":"S. Agrawal, S. Kumari, and S. Yamada, Pseudorandom Multi-Input Functional Encryption and Applications, Cryptology ePrint Archive, Report 2024\/1720, https:\/\/eprint.iacr.org\/2024\/1720 (2024)."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03810-6_18"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38551-3_17"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68382-4_13"},{"key":"ref7","unstructured":"P. Ananth, D. Boneh, S. Garg, A. Sahai, and M. Zhandry, Differing-Inputs Obfuscation and Applications, Cryptology ePrint Archive, Report 2013\/689, https:\/\/eprint.iacr.org\/2013\/689 (2013)."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22963-3_6"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63715-0_9"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49096-9_6"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44647-8_1"},{"key":"ref13","unstructured":"N. Bitansky and R. Garg, Succinct Randomized Encodings from Non-compact Functional Encryption, Faster and Simpler, Cryptology ePrint Archive, Report 2024\/1815, https:\/\/eprint.iacr.org\/2024\/1815 (2024)."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20465-4_10"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_30"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19571-6_16"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-42045-0_15"},{"key":"ref18","first-page":"309","volume-title":"Innovations in Theoretical Computer Science 2012","author":"Brakerski Z.","year":"2012"},{"key":"ref19","first-page":"91","volume-title":"Theory of Cryptography 2024","author":"Brakerski Z.","year":"2024"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70500-2_10"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46497-7_1"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_13"},{"key":"ref24","first-page":"418","volume-title":"Asiacrypt 2024","author":"Brzuska C.","year":"2024"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46497-7_19"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96881-0_20"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46800-5_1"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00032"},{"key":"ref29","first-page":"238","volume-title":"Asiacrypt 2024","author":"Cini V.","year":"2024"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90453-1_9"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68382-4_4"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.13"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_27"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451070"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_30"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488678"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_11"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488677"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_25"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746576"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64375-1_9"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_14"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.62"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"R. Goyal, V. Koppula, and B. Waters, Lockable Obfuscation, Cryptology ePrint Archive, Report 2017\/274, 2017, pp. 612\u2013621, https:\/\/eprint.iacr.org\/2017\/274.","DOI":"10.1109\/FOCS.2017.62"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180418"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06944-4_24"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84245-1_23"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00031"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-58723-8_15"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30545-0_8"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30620-4_16"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451093"},{"key":"ref56","first-page":"670","volume-title":"EUROCRYPT 2022, Part I, Lecture Notes in Comput. Sci. 13275","author":"Jain A.","year":"2022"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_17"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22318-1_24"},{"key":"ref59","doi-asserted-by":"crossref","unstructured":"D. Micciancio and C. Peikert, Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Cryptology ePrint Archive, Report 2011\/501, 2012, pp. 700\u2013718, https:\/\/eprint.iacr.org\/2011\/501.","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"ref61","unstructured":"A. O\u2019Neill, Definitional Issues in Functional Encryption, Cryptology ePrint Archive, Report 2010\/556, 2010, https:\/\/eprint.iacr.org\/2010\/556."},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00086"},{"key":"ref63","first-page":"859","author":"Quach W.","year":"2018","journal-title":"Cryptology ePrint Archive, Report 2018\/409"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"ref65","first-page":"169","author":"Rivest R. L.","year":"1978","journal-title":"Foundationsof Secure Computation"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1145\/1866307.1866359"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1007\/11426639_27"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_19"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22963-3_7"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22318-1_23"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-07085-3_8"},{"key":"ref72","first-page":"178","volume-title":"CRYPTO 2024, Part III, Lecture Notes in Comput. Sci. 14922","author":"Wee H.","year":"2024"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77883-5_5"},{"key":"ref74","unstructured":"D. Wheeler, quote, \u201cAll problems in computer science can be solved by another level of indirection.\u201d."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1629316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:12Z","timestamp":1787337792000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1629316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,17]]},"references-count":74,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M1629316"],"URL":"https:\/\/doi.org\/10.1137\/24m1629316","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,17]]}}}