{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T20:45:41Z","timestamp":1791665141210,"version":"4.3.4"},"reference-count":61,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits $C_0$ and $C_1$ of similar size, the obfuscations of $C_0$ and $C_1$ should be computationally indistinguishable. In functional encryption, ciphertexts encrypt inputs $x$ and keys are issued for circuits $C$. Using the key $\\mathrm{SK}_C$ to decrypt a ciphertext $\\mathrm{CT}_x={\\sf Enc}(x)$ yields the value $C(x)$ but does not reveal anything else about $x$. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: (1) We describe a candidate construction for indistinguishability obfuscation for $\\mathbf{NC}^1$ circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call multilinear jigsaw puzzles. (2) We show how to use indistinguishability obfuscation for $\\mathbf{NC}^1$ together with fully homomorphic encryption (with decryption in $\\mathbf{NC}^1$) to achieve indistinguishability obfuscation for all circuits. (3) Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and noninteractive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.<\/jats:p>","DOI":"10.1137\/14095772x","type":"journal-article","created":{"date-parts":[[2016,6,29]],"date-time":"2016-06-29T17:28:58Z","timestamp":1467221338000},"page":"882-929","source":"Crossref","is-referenced-by-count":179,"title":["Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits"],"prefix":"10.1137","volume":"45","author":[{"given":"Sanjam","family":"Garg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Craig","family":"Gentry","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shai","family":"Halevi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mariana","family":"Raykova","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brent","family":"Waters","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,6,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"S. Arora and B. Barak,\n                      Computational Complexity-A Modern Approach\n                      , Cambridge University Press, Cambridge, 2009.","DOI":"10.1017\/CBO9780511804090"},{"key":"atypb2","first-page":"528","volume":"2015","author":"Applebaum B.","year":"2015","journal-title":"TCC"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"S. Agrawal, D. Mandell Freeman, and V. Vaikuntanathan,\n                      Functional encryption for inner product predicates from learning with errors\n                      , in Proceedings of ASIACRYPT, 2011.","DOI":"10.1007\/978-3-642-25385-0_2"},{"key":"atypb4","first-page":"646","author":"Ananth P. V.","year":"2014","journal-title":"AZ"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Agrawal, S. Gorbunov, V. Vaikuntanathan, and H. Wee,\n                      Functional encryption: New perspectives and lower bounds\n                      , in Proceedings of CRYPTO, 2013.","DOI":"10.1007\/978-3-642-40084-1_28"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"D. A. Barrington,\n                      Bounded-width polynomial-size branching programs recognize exactly those languages in $nc_1$\n                      , in Proceedings of STOC, 1986.","DOI":"10.1145\/12130.12131"},{"key":"atypb7","first-page":"506","author":"Boneh D.","year":"2004","journal-title":"Proceedings of EUROCRYPT"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"D. Boneh and M. K. Franklin,\n                      Identity-based encryption from the weil pairing\n                      , in Proceedings of CRYPTO, 2001.","DOI":"10.1007\/3-540-44647-8_13"},{"key":"atypb9","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/62212.62222","author":"Blum M.","year":"1988","journal-title":"Proceedings of STOC"},{"key":"atypb10","first-page":"1","author":"Barak B.","year":"2001","journal-title":"Proceedings of CRYPTO"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160159"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, C. Gentry, and V. Vaikuntanathan,\n                      (Leveled) fully homomorphic encryption without bootstrapping\n                      , in Proceedings of ITCS, 2012.","DOI":"10.1145\/2090236.2090262"},{"key":"atypb13","first-page":"563","author":"Boneh D.","year":"2015","journal-title":"Bulgaria"},{"key":"atypb14","first-page":"37","author":"Ben-Or M.","year":"1988","journal-title":"Proceedings of CRYPTO"},{"key":"atypb15","first-page":"868","author":"Brakerski Z.","year":"2012","journal-title":"Proceedings of CRYPTO"},{"key":"atypb16","first-page":"573","author":"Boneh D.","year":"2006","journal-title":"Proceedings of EUROCRYPT"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19571-6_16"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Z. Brakerski and V. Vaikuntanathan,\n                      Fully homomorphic encryption from ring-lwe and security for key dependent messages\n                      , in Proceedings of CRYPTO, 2011.","DOI":"10.1007\/978-3-642-22792-9_29"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70936-7_29"},{"key":"atypb20","unstructured":"R. Canetti and V. Vaikuntanathan,\n                      private communication\n                      , 2007."},{"key":"atypb21","first-page":"257","author":"Chor B.","year":"1994","journal-title":"Proceedings of CRYPTO"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"A. De Caro, V. Iovino, A. Jain, A. O'Neill, O. Paneth, and G. Persiano,\n                      On the achievability of simulation-based security for functional encryption\n                      , in Proceedings of CRYPTO, 2013.","DOI":"10.1007\/978-3-642-40084-1_29"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"J.S. Coron, T. Lepoint, and M. Tibouchi,\n                      Practical multilinear maps over the integers\n                      , in Proceedings of CRYPTO, 2013.","DOI":"10.1007\/978-3-642-40041-4_26"},{"key":"atypb24","first-page":"487","author":"Coron J.-S.","year":"2011","journal-title":"Proceedings of CRYPTO"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45325-3_32"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792230010"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100272"},{"key":"atypb28","first-page":"169","author":"Gentry C.","year":"2009","journal-title":"Proceedings of STOC"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, and S. Halevi,\n                      Candidate multilinear maps from ideal lattices\n                      , in Proceedings of EUROCRYPT, 2013.","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"atypb30","first-page":"40","author":"Garg S.","year":"2013","journal-title":"IEEE Computer Society"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi, A. Sahai, and B. Waters,\n                      Attribute-based encryption for circuits from multilinear maps\n                      , in Proceedings of CRYPTO, 2013.","DOI":"10.1007\/978-3-642-40084-1_27"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, A. Sahai, and B. Waters,\n                      Witness encryption and its applications\n                      , in Proceedings of STOC, 2013.","DOI":"10.1145\/2488608.2488667"},{"key":"atypb33","first-page":"553","author":"Goldwasser S.","year":"2005","journal-title":"Proceedings of FOCS"},{"key":"atypb34","unstructured":"S. Goldwasser, Y. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich,\n                      Succinct functional encryption and applications: Reusable garbled circuits and beyond\n                      , in Proceedings of STOC, 2013."},{"key":"atypb35","first-page":"218","author":"Goldreich O.","year":"1987","journal-title":"Proceedings of STOC"},{"key":"atypb36","first-page":"339","author":"Groth J.","year":"2006","journal-title":"New York"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"V. Goyal, O. Pandey, A. Sahai, and B. Waters,\n                      Attribute-based encryption for fine-grained access control of encrypted data\n                      , in Proceedings of CCS, 2006.","DOI":"10.1145\/1180405.1180418"},{"key":"atypb38","first-page":"197","author":"Gentry C.","year":"2008","journal-title":"Proceedings of STOC"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70936-7_11"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"C. Gentry, A. Sahai, and B. Waters,\n                      Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based\n                      , in Proceedings of CRYPTO, 2013.","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"S. Gorbunov, V. Vaikuntanathan, and H. Wee,\n                      Functional encryption with bounded collusions via multi-party computation\n                      , in Proceedings of CRYPTO, 2012.","DOI":"10.1007\/978-3-642-32009-5_11"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"S. Gorbunov, V. Vaikuntanathan, and H. Wee,\n                      Attribute-based encryption for circuits\n                      , in Proceedings of STOC, 2013.","DOI":"10.1145\/2488608.2488677"},{"key":"atypb43","first-page":"443","author":"Hada S.","year":"2000","journal-title":"New York"},{"key":"atypb44","unstructured":"Y. Ishai,\n                      private communication\n                      , 2013."},{"key":"atypb45","first-page":"20","author":"Kilian J.","year":"1988","journal-title":"ACM"},{"key":"atypb46","unstructured":"J. Katz, A. Sahai, and B. Waters,\n                      Predicate encryption supporting disjunctions, polynomial equations, and inner products\n                      , in Proceedings of EUROCRYPT, 2008."},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214086"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100273"},{"key":"atypb50","unstructured":"A. O'Neill,\n                      Definitional issues in functional encryption\n                      , Cryptology ePrint Archive, Report 2010\/556, 2010."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_24"},{"key":"atypb52","first-page":"543","author":"Sahai A.","year":"1999","journal-title":"Proceedings of FOCS"},{"key":"atypb53","first-page":"47","author":"Shamir A.","year":"1984","journal-title":"Proceedings of CRYPTO"},{"key":"atypb54","first-page":"463","author":"Sahai A.","year":"2010","journal-title":"Proceedings of CCS"},{"key":"atypb55","first-page":"27","author":"Stehl\u00e9 D.","year":"2011","journal-title":"Proceedings of EUROCRYPT"},{"key":"atypb56","first-page":"457","author":"Sahai A.","year":"2005","journal-title":"Proceedings of EUROCRYPT"},{"key":"atypb57","unstructured":"A. Sahai and B. Waters,\n                      private communication\n                      , 2006."},{"key":"atypb58","unstructured":"A. Sahai and B. Waters,\n                      Slides on Functional Encryption\n                      , http:\/\/www.cs.utexas.edu\/\\string bwaters\/presentations\/files\/functional.ppt (2008)."},{"key":"atypb59","first-page":"44","author":"Song D. X.","year":"2000","journal-title":"Proceedings of the IEEE Symposium on Security and Privacy"},{"key":"atypb60","first-page":"24","author":"van Dijk M.","year":"2010","journal-title":"Proceedings of EUROCRYPT"},{"key":"atypb61","first-page":"439","author":"Zimmerman J.","year":"2015","journal-title":"Bulgaria"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14095772X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:08:39Z","timestamp":1787339319000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14095772X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/14095772X"],"URL":"https:\/\/doi.org\/10.1137\/14095772x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}