{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T18:41:12Z","timestamp":1658774472634},"reference-count":94,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s00145-022-09431-5","type":"journal-article","created":{"date-parts":[[2022,7,6]],"date-time":"2022-07-06T02:02:41Z","timestamp":1657072961000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Compressing Obfuscation"],"prefix":"10.1007","volume":"35","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Sirkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,6]]},"reference":[{"key":"9431_CR1","doi-asserted-by":"crossref","unstructured":"P. Ananth, A. Jain, M. Naor, A. Sahai, E. Yogev, Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption, in Advances in Cryptology - CRYPTO (2016), pp. 491\u2013520","DOI":"10.1007\/978-3-662-53008-5_17"},{"key":"9431_CR2","doi-asserted-by":"crossref","unstructured":"P. Ananth, A. Jain, A. Sahai, Robust transforming combiners from indistinguishability obfuscation to functional encryption, in Advances in Cryptology - EUROCRYPT (2017), pp. 91\u2013121","DOI":"10.1007\/978-3-319-56620-7_4"},{"key":"9431_CR3","doi-asserted-by":"crossref","unstructured":"P. Ananth, A. Jain, Indistinguishability obfuscation from compact functional encryption, in Advances in Cryptology - CRYPTO (2015), pp. 308\u2013326","DOI":"10.1007\/978-3-662-47989-6_15"},{"key":"9431_CR4","doi-asserted-by":"crossref","unstructured":"P. Ananth, A. Sahai, Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps, in Advances in Cryptology - EUROCRYPT (2017), pp. 152\u2013181","DOI":"10.1007\/978-3-319-56620-7_6"},{"key":"9431_CR5","doi-asserted-by":"crossref","unstructured":"P.V. Ananth, D. Gupta, Y. Ishai, A. Sahai, Optimizing obfuscation: Avoiding barrington\u2019s theorem, in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (2014), pp. 646\u2013658","DOI":"10.1145\/2660267.2660342"},{"issue":"4","key":"9431_CR6","first-page":"319","volume":"2","author":"D Angluin","year":"1987","unstructured":"D. Angluin, Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1987)","journal-title":"Mach. Learn."},{"key":"9431_CR7","unstructured":"D. Apon, N. D\u00f6ttling, S. Garg, P. Mukherjee, Cryptanalysis of indistinguishability obfuscations of circuits over GGH13, in 44th International Colloquium on Automata, Languages, and Programming, ICALP (2017), pp. 38:1\u201338:16"},{"key":"9431_CR8","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Z. Brakerski, Obfuscating circuits via composite-order graded encoding, in Theory of Cryptography - TCC (2015), pp. 528\u2013556","DOI":"10.1007\/978-3-662-46497-7_21"},{"issue":"6","key":"9431_CR9","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1137\/15M1034064","volume":"45","author":"G Asharov","year":"2016","unstructured":"G. Asharov, G. Segev, Limits on the power of indistinguishability obfuscation and functional encryption. SIAM J. Comput. 45(6), 2117\u20132176 (2016)","journal-title":"SIAM J. Comput."},{"key":"9431_CR10","doi-asserted-by":"crossref","unstructured":"G. Asharov, G. Segev, On constructing one-way permutations from indistinguishability obfuscation, in Theory of Cryptography Conference (2016)","DOI":"10.1007\/978-3-662-49099-0_19"},{"issue":"6","key":"9431_CR11","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/0898-1221(81)90029-8","volume":"7","author":"CA Asmuth","year":"1981","unstructured":"C.A. Asmuth, G.R. Blakley, An efficient algorithm for constructing a cryptosystem which is harder to break than two other cryptosystems. Comput. Math. Appl. 7(6), 447 \u2013 450 (1981)","journal-title":"Comput. Math. Appl."},{"key":"9431_CR12","doi-asserted-by":"crossref","unstructured":"B. Barak, Z. Brakerski, I. Komargodski, P.K. Kothari, Limits on low-degree pseudorandom generators (or: Sum-of-squares meets program obfuscation), in Advances in Cryptology - EUROCRYPT (2018), pp. 649\u2013679","DOI":"10.1007\/978-3-319-78375-8_21"},{"key":"9431_CR13","doi-asserted-by":"crossref","unstructured":"B. Barak, S. Garg, Y.T. Kalai, O. Paneth, A. Sahai, Protecting obfuscation against algebraic attacks, in Advances in Cryptology - EUROCRYPT (2014), pp. 221\u2013238","DOI":"10.1007\/978-3-642-55220-5_13"},{"key":"9431_CR14","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K. Yang, On the (im)possibility of obfuscating programs. J. ACM 59(2), 6:1\u20136:48 (2012)","DOI":"10.1145\/2160158.2160159"},{"key":"9431_CR15","doi-asserted-by":"crossref","unstructured":"N. Bitansky, A. Degwekar, V. Vaikuntanathan, Structure vs. hardness through the obfuscation lens, in Advances in Cryptology - CRYPTO (2017), pp. 696\u2013723","DOI":"10.1007\/978-3-319-63688-7_23"},{"key":"9431_CR16","doi-asserted-by":"crossref","unstructured":"N. Bitansky, H. Lin, O. Paneth, On removing graded encodings from functional encryption, in Advances in Cryptology - EUROCRYPT (2017), pp. 3\u201329","DOI":"10.1007\/978-3-319-56614-6_1"},{"key":"9431_CR17","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Nishimaki, A. Passel\u00e8gue, D. Wichs, From Cryptomania to Obfustopia through secret-key functional encryption, in Theory of Cryptography - TCC (2016), pp. 391\u2013418","DOI":"10.1007\/978-3-662-53644-5_15"},{"key":"9431_CR18","doi-asserted-by":"crossref","unstructured":"N. Bitansky, O. Paneth, Zaps and non-interactive witness indistinguishability from indistinguishability obfuscation, in Theory of Cryptography - TCC (2015), pp. 401\u2013427","DOI":"10.1007\/978-3-662-46497-7_16"},{"key":"9431_CR19","doi-asserted-by":"crossref","unstructured":"N. Bitansky, O. Paneth, D. Wichs, Perfect structure on the edge of chaos - trapdoor permutations from indistinguishability obfuscation, in Theory of Cryptography - TCC (2016), pp. 474\u2013502","DOI":"10.1007\/978-3-662-49096-9_20"},{"key":"9431_CR20","doi-asserted-by":"crossref","unstructured":"N. Bitansky, V. Vaikuntanathan, Indistinguishability obfuscation from functional encryption, in IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS (2015), pp. 171\u2013190","DOI":"10.1109\/FOCS.2015.20"},{"key":"9431_CR21","doi-asserted-by":"crossref","unstructured":"N. Bitansky, V. Vaikuntanathan, Indistinguishability obfuscation: From approximate to exact, in Theory of Cryptography - TCC (2016), pp. 67\u201395","DOI":"10.1007\/978-3-662-49096-9_4"},{"key":"9431_CR22","doi-asserted-by":"crossref","unstructured":"N. Bitansky, V. Vaikuntanathan, A note on perfect correctness by derandomization, in Advances in Cryptology - EUROCRYPT (2017), pp. 592\u2013606","DOI":"10.1007\/978-3-319-56614-6_20"},{"key":"9431_CR23","doi-asserted-by":"crossref","unstructured":"D. Boneh, C. Gentry, S. Gorbunov, S. Halevi, V. Nikolaenko, G. Segev, V. Vaikuntanathan, D. Vinayagamurthy, Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits, in Advances in Cryptology - EUROCRYPT (2014), pp. 533\u2013556","DOI":"10.1007\/978-3-642-55220-5_30"},{"issue":"11","key":"9431_CR24","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/2366316.2366333","volume":"55","author":"D Boneh","year":"2012","unstructured":"D. Boneh, A. Sahai, B. Waters, Functional encryption: a new vision for public-key cryptography. Commun. ACM 55(11), 56\u201364 (2012)","journal-title":"Commun. ACM"},{"key":"9431_CR25","doi-asserted-by":"crossref","unstructured":"D. Boneh, B. Waters, Constrained pseudorandom functions and their applications, in Advances in Cryptology - ASIACRYPT (2013), pp. 280\u2013300","DOI":"10.1007\/978-3-642-42045-0_15"},{"key":"9431_CR26","first-page":"930","volume":"2014","author":"D Boneh","year":"2014","unstructured":"D. Boneh, D.J. Wu, J. Zimmerman, Immunizing multilinear maps against zeroizing attacks. IACR Cryptology ePrint Archive 2014:930 (2014)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"9431_CR27","doi-asserted-by":"crossref","unstructured":"E. Boyle, S. Goldwasser, I. Ivan, Functional signatures and pseudorandom functions, in Public-Key Cryptography - PKC (2014), pp. 501\u2013519","DOI":"10.1007\/978-3-642-54631-0_29"},{"key":"9431_CR28","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, C. Brzuska, N. Fleischhacker, On statistically secure obfuscation with approximate correctness, in Advances in Cryptology - CRYPTO (2016), pp. 551\u2013578","DOI":"10.1007\/978-3-662-53008-5_19"},{"key":"9431_CR29","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, N. D\u00f6ttling, S. Garg, G. Malavolta, Candidate io from homomorphic encryption schemes, in EUROCRYPT (1), volume 12105 of Lecture Notes in Computer Science (Springer, 2020), pp. 79\u2013109","DOI":"10.1007\/978-3-030-45721-1_4"},{"key":"9431_CR30","first-page":"1024","volume":"2020","author":"Z Brakerski","year":"2020","unstructured":"Z. Brakerski, N. D\u00f6ttling, S. Garg, G. Malavolta, Factoring and pairings are not necessary for io: Circular-secure LWE suffices, IACR Cryptol. ePrint Arch., 2020:1024 (2020)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"9431_CR31","first-page":"874","volume":"2017","author":"Z Brakerski","year":"2017","unstructured":"Z. Brakerski, A. Jain, I. Komargodski, A. Passel\u00e8gue, D. Wichs, Non-trivial witness encryption and null-io from standard assumptions, IACR Cryptology ePrint Archive, 2017:874 (2017)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"9431_CR32","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, J. Katz, G. Segev, A. Yerukhimovich, Limits on the power of zero-knowledge proofs in cryptographic constructions, in Theory of Cryptography - TCC (2011), pp. 559\u2013578","DOI":"10.1007\/978-3-642-19571-6_34"},{"key":"9431_CR33","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, G.N. Rothblum, Virtual black-box obfuscation for all circuits via generic graded encoding, in Theory of Cryptography - TCC (2014), pp. 1\u201325","DOI":"10.1007\/978-3-642-54242-8_1"},{"issue":"4","key":"9431_CR34","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"NH Bshouty","year":"1996","unstructured":"N.H. Bshouty, C. Tamon, On the fourier spectrum of monotone functions. J. ACM 43(4), 747\u2013770 (1996)","journal-title":"J. ACM"},{"key":"9431_CR35","unstructured":"M.L. Carmosino, R. Impagliazzo, V. Kabanets, A. Kolokolova, Learning algorithms from natural proofs, in 31st Conference on Computational Complexity, CCC (2016), pp. 10:1\u201310:24"},{"key":"9431_CR36","unstructured":"M.L. Carmosino, R. Impagliazzo, V. Kabanets, A. Kolokolova, Agnostic learning from tolerant natural proofs, in Approximation, Randomization, and Combinatorial Optimization, APPROX\/RANDOM (2017), pp. 35:1\u201335:19"},{"issue":"2","key":"9431_CR37","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00037-015-0100-0","volume":"24","author":"R Chen","year":"2015","unstructured":"R. Chen, V. Kabanets, A. Kolokolova, R. Shaltiel, D. Zuckerman, Mining circuit lower bound proofs for meta-algorithms. Comput. Complex. 24(2), 333\u2013392 (2015)","journal-title":"Comput. Complex."},{"key":"9431_CR38","doi-asserted-by":"crossref","unstructured":"Y. Chen, C. Gentry, S. Halevi, Cryptanalyses of candidate branching program obfuscators, in Advances in Cryptology - EUROCRYPT (2017), pp. 278\u2013307","DOI":"10.1007\/978-3-319-56617-7_10"},{"key":"9431_CR39","doi-asserted-by":"crossref","unstructured":"J.H. Cheon, K. Han, C. Lee, H. Ryu, D. Stehl\u00e9, Cryptanalysis of the multilinear map over the integers, in Advances in Cryptology - EUROCRYPT (2015), pp. 3\u201312","DOI":"10.1007\/978-3-662-46800-5_1"},{"key":"9431_CR40","doi-asserted-by":"crossref","unstructured":"J.-S. Coron, C. Gentry, S. Halevi, T. Lepoint, H.K. Maji, E. Miles, M. Raykova, A. Sahai, M. Tibouchi, Zeroizing without low-level zeroes: New MMAP attacks and their limitations, in Advances in Cryptology - CRYPTO (2015), pp. 247\u2013266","DOI":"10.1007\/978-3-662-47989-6_12"},{"key":"9431_CR41","doi-asserted-by":"crossref","unstructured":"J.-S. Coron, T. Lepoint, M. Tibouchi, Practical multilinear maps over the integers, in Advances in Cryptology - CRYPTO (2013), pp. 476\u2013493","DOI":"10.1007\/978-3-642-40041-4_26"},{"key":"9431_CR42","doi-asserted-by":"crossref","unstructured":"Jean-S\u00e9bastien Coron, Tancr\u00e8de Lepoint, Mehdi Tibouchi. New multilinear maps over the integers, in Advances in Cryptology - CRYPTO (2015), pp. 267\u2013286","DOI":"10.1007\/978-3-662-47989-6_13"},{"key":"9431_CR43","unstructured":"W. Diffie, M.E. Hellman, Multiuser cryptographic techniques, in American Federation of Information Processing Societies (1976), pp. 109\u2013112"},{"key":"9431_CR44","doi-asserted-by":"crossref","unstructured":"M. Fischlin, A. Herzberg, H.B. Noon, H. Shulman, Obfuscation combiners, in Advances in Cryptology - CRYPTO (2016), pp. 521\u2013550","DOI":"10.1007\/978-3-662-53008-5_18"},{"key":"9431_CR45","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, B. Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits, in 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS (IEEE Computer Society, 2013), pp. 40\u201349","DOI":"10.1109\/FOCS.2013.13"},{"key":"9431_CR46","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, A. Sahai, B. Waters, Witness encryption and its applications, in Symposium on Theory of Computing Conference, STOC (2013), pp. 467\u2013476","DOI":"10.1145\/2488608.2488667"},{"key":"9431_CR47","doi-asserted-by":"crossref","unstructured":"S. Garg, M. Hajiabadi, M. Mahmoody, A. Mohammed, Limits on the power of garbling techniques for public-key encryption, in Advances in Cryptology - CRYPTO (2018), pp. 335\u2013364","DOI":"10.1007\/978-3-319-96878-0_12"},{"key":"9431_CR48","doi-asserted-by":"crossref","unstructured":"Sanjam Garg, Mohammad Mahmoody, Ameer Mohammed. Lower bounds on obfuscation from all-or-nothing encryption primitives, in Advances in Cryptology - CRYPTO (2017), pp. 661\u2013695","DOI":"10.1007\/978-3-319-63688-7_22"},{"key":"9431_CR49","doi-asserted-by":"crossref","unstructured":"S. Garg, M. Mahmoody, A. Mohammed, When does functional encryption imply obfuscation? In Theory of Cryptography - TCC (2017), pp. 82\u2013115","DOI":"10.1007\/978-3-319-70500-2_4"},{"key":"9431_CR50","doi-asserted-by":"crossref","unstructured":"R. Gay, R. Pass, Indistinguishability obfuscation from circular security, in STOC (ACM, 2021), pp. 736\u2013749","DOI":"10.1145\/3406325.3451070"},{"key":"9431_CR51","doi-asserted-by":"crossref","unstructured":"C. Gentry, S. Gorbunov, S. Halevi, Graph-induced multilinear maps from lattices, in Theory of Cryptography - TCC (2015), pp. 498\u2013527","DOI":"10.1007\/978-3-662-46497-7_20"},{"key":"9431_CR52","doi-asserted-by":"crossref","unstructured":"C. Gentry, A.B. Lewko, A. Sahai, B. Waters, Indistinguishability obfuscation from the multilinear subgroup elimination assumption, in IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS (2015), pp. 151\u2013170","DOI":"10.1109\/FOCS.2015.19"},{"key":"9431_CR53","unstructured":"O. Goldreich, The Foundations of Cryptography - Volume 1, Basic Techniques, chapter 4.10.3.1 (Cambridge University Press, 2001)"},{"issue":"4","key":"9431_CR54","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM 33(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"9431_CR55","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, S.D. Gordon, V. Goyal, A. Jain, J. Katz, F.-H. Liu, A. Sahai, E. Shi, H.-S. Zhou, Multi-input functional encryption, in Advances in Cryptology - EUROCRYPT (2014), pp. 578\u2013602","DOI":"10.1007\/978-3-642-55220-5_32"},{"key":"9431_CR56","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, Y.T. Kalai, R.A. Popa, V. Vaikuntanathan, N. Zeldovich, Reusable garbled circuits and succinct functional encryption, in Symposium on Theory of Computing Conference, STOC (2013), pp. 555\u2013564","DOI":"10.1145\/2488608.2488678"},{"key":"9431_CR57","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, G.N. Rothblum, On best-possible obfuscation, in Theory of Cryptography - TCC (2007), pp. 194\u2013213","DOI":"10.1007\/978-3-540-70936-7_11"},{"key":"9431_CR58","doi-asserted-by":"crossref","unstructured":"S. Gorbunov, V. Vaikuntanathan, H. Wee, Functional encryption with bounded collusions via multi-party computation, in Advances in Cryptology - CRYPTO (2012), pp. 162\u2013179","DOI":"10.1007\/978-3-642-32009-5_11"},{"key":"9431_CR59","unstructured":"V. Guruswami, A. Rudra, M. Sudan, Essential coding theory, 2013. https:\/\/cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book\/index.html. Accessed May 31, 2018"},{"key":"9431_CR60","doi-asserted-by":"crossref","unstructured":"V. Guruswami, M. Sudan, List decoding algorithms for certain concatenated codes, in Proceedings of the 32nd annual ACM symposium on Theory of computing, STOC (ACM, 2000), pp. 181\u2013190","DOI":"10.1145\/335305.335327"},{"key":"9431_CR61","doi-asserted-by":"crossref","unstructured":"D. Harnik, J. Kilian, M. Naor, O. Reingold, A. Rosen, On robust combiners for oblivious transfer and other primitives, in Advances in Cryptology - EUROCRYPT (2005), pp. 96\u2013113","DOI":"10.1007\/11426639_6"},{"issue":"4","key":"9431_CR62","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"J. H\u00e5stad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9431_CR63","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2007.05.018","volume":"384","author":"L Hellerstein","year":"2007","unstructured":"L. Hellerstein, R.A. Servedio, On PAC learning algorithms for rich boolean function classes. Theor. Comput. Sci. 384(1), 66\u201376 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9431_CR64","doi-asserted-by":"crossref","unstructured":"A. Herzberg, On tolerant cryptographic constructions, in Topics in Cryptology - CT-RSA (2005), pp. 172\u2013190","DOI":"10.1007\/978-3-540-30574-3_13"},{"issue":"2","key":"9431_CR65","doi-asserted-by":"publisher","first-page":"159","DOI":"10.3233\/JCS-2009-0336","volume":"17","author":"A Herzberg","year":"2009","unstructured":"A. Herzberg, Folklore, practice and theory of robust combiners. J. Comput. Secur. 17(2), 159\u2013189 (2009)","journal-title":"J. Comput. Secur."},{"key":"9431_CR66","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way permutations, in Proceedings of the 21st annual ACM symposium on Theory of computing, STOC (ACM, 1989), pp. 44\u201361","DOI":"10.1145\/73007.73012"},{"issue":"2\u20133","key":"9431_CR67","first-page":"115","volume":"17","author":"MJ Kearns","year":"1994","unstructured":"M.J. Kearns, R.E. Schapire, L. Sellie, Toward efficient agnostic learning. Mach. Learn. 17(2-3), 115\u2013141 (1994)","journal-title":"Mach. Learn."},{"key":"9431_CR68","doi-asserted-by":"crossref","unstructured":"A. Kiayias, S. Papadopoulos, N. Triandopoulos, T. Zacharias, Delegatable pseudorandom functions and applications, in Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security (ACM, 2013), pp. 669\u2013684","DOI":"10.1145\/2508859.2516668"},{"key":"9431_CR69","doi-asserted-by":"crossref","unstructured":"S. Kim, D.J. Wu, Multi-theorem preprocessing nizks from lattices, in Advances in Cryptology - CRYPTO (2018)","DOI":"10.1007\/978-3-319-96881-0_25"},{"key":"9431_CR70","doi-asserted-by":"crossref","unstructured":"F. Kitagawa, R. Nishimaki, K. Tanaka, Obfustopia built on secret-key functional encryption, in Advances in Cryptology - EUROCRYPT (2018), pp. 603\u2013648","DOI":"10.1007\/978-3-319-78375-8_20"},{"key":"9431_CR71","doi-asserted-by":"crossref","unstructured":"I. Komargodski, T. Moran, M. Naor, R. Pass, A. Rosen, E. Yogev, One-way functions and (im)perfect obfuscation, in 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2014), pp. 374\u2013383","DOI":"10.1109\/FOCS.2014.47"},{"issue":"4","key":"9431_CR72","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"LA Levin","year":"1987","unstructured":"L.A. Levin, One-way functions and pseudorandom generators. Combinatorica 7(4), 357\u2013363 (1987)","journal-title":"Combinatorica"},{"key":"9431_CR73","doi-asserted-by":"crossref","unstructured":"H. Lin, Indistinguishability obfuscation from constant-degree graded encoding schemes, in Advances in Cryptology - EUROCRYPT (2016), pp. 28\u201357","DOI":"10.1007\/978-3-662-49890-3_2"},{"key":"9431_CR74","doi-asserted-by":"crossref","unstructured":"H. Lin, Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs, in Advances in Cryptology - CRYPTO (2017), pp. 599\u2013629","DOI":"10.1007\/978-3-319-63688-7_20"},{"key":"9431_CR75","doi-asserted-by":"crossref","unstructured":"H. Lin, R. Pass, K. Seth, S. Telang, Indistinguishability obfuscation with non-trivial efficiency, in Public-Key Cryptography - PKC (2016), pp. 447\u2013462","DOI":"10.1007\/978-3-662-49387-8_17"},{"key":"9431_CR76","doi-asserted-by":"crossref","unstructured":"H. Lin, R. Pass, K. Seth, S. Telang, Output-compressing randomized encodings and applications, in Theory of Cryptography - TCC (2016), pp. 96\u2013124","DOI":"10.1007\/978-3-662-49096-9_5"},{"key":"9431_CR77","doi-asserted-by":"crossref","unstructured":"H. Lin, V. Vaikuntanathan, Indistinguishability obfuscation from ddh-like assumptions on constant-degree graded encodings, in IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS (2016), pp. 11\u201320","DOI":"10.1109\/FOCS.2016.11"},{"key":"9431_CR78","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, Noam Nisan. Constant depth circuits, fourier transform, and learnability, in 30th Annual Symposium on Foundations of Computer Science, FOCS (1989), pp. 574\u2013579","DOI":"10.1109\/SFCS.1989.63537"},{"key":"9431_CR79","doi-asserted-by":"crossref","unstructured":"Q. Liu, M. Zhandry, Decomposable obfuscation: A framework for building applications of obfuscation from polynomial hardness, in Theory of Cryptography - TCC (2017), pp. 138\u2013169","DOI":"10.1007\/978-3-319-70500-2_6"},{"key":"9431_CR80","doi-asserted-by":"crossref","unstructured":"A. Lombardi, V. Vaikuntanathan, Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation, in Theory of Cryptography - TCC (2017), pp. 119\u2013137","DOI":"10.1007\/978-3-319-70500-2_5"},{"key":"9431_CR81","doi-asserted-by":"crossref","unstructured":"M. Mahmoody, A. Mohammed, S. Nematihaji, R. Pass, A. Shelat, Lower bounds on assumptions behind indistinguishability obfuscation, in Theory of Cryptography - TCC (2016), pp. 49\u201366","DOI":"10.1007\/978-3-662-49096-9_3"},{"key":"9431_CR82","doi-asserted-by":"crossref","unstructured":"M. Mahmoody, D. Xiao, On the power of randomized reductions and the checkability of SAT, in Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC (IEEE Computer Society, 2010), pp. 64\u201375","DOI":"10.1109\/CCC.2010.16"},{"key":"9431_CR83","doi-asserted-by":"crossref","unstructured":"S. Micali, C. Peikert, M. Sudan, D.A Wilson, Optimal error correction against computationally bounded noise, in Theory of Cryptography - TCC (Springer, 2005), pp. 1\u201316","DOI":"10.1007\/978-3-540-30576-7_1"},{"key":"9431_CR84","doi-asserted-by":"crossref","unstructured":"E. Miles, A. Sahai, M. Zhandry, Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13, in Advances in Cryptology - CRYPTO (2016), pp. 629\u2013658","DOI":"10.1007\/978-3-662-53008-5_22"},{"issue":"2","key":"9431_CR85","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M Naor","year":"1991","unstructured":"M. Naor, Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151\u2013158 (1991)","journal-title":"J. Cryptol."},{"issue":"1","key":"9431_CR86","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jcss.1999.1664","volume":"60","author":"T Okamoto","year":"2000","unstructured":"T. Okamoto, On relationships between statistical zero-knowledge proofs. J. Comput. Syst. Sci. 60(1), 47\u2013108 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"9431_CR87","first-page":"556","volume":"2010","author":"A O\u2019Neill","year":"2010","unstructured":"A. O\u2019Neill, Definitional issues in functional encryption. IACR Cryptology ePrint Archive 2010:556 (2010)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"9431_CR88","doi-asserted-by":"crossref","unstructured":"R. Pass, K. Seth, S. Telang, Indistinguishability obfuscation from semantically-secure multilinear encodings, in Advances in Cryptology - CRYPTO (2014), pp. 500\u2013517","DOI":"10.1007\/978-3-662-44371-2_28"},{"issue":"2","key":"9431_CR89","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A Sahai","year":"2003","unstructured":"A. Sahai, S.P. Vadhan, A complete problem for statistical zero knowledge. J. ACM 50(2), 196\u2013249 (2003)","journal-title":"J. ACM"},{"key":"9431_CR90","doi-asserted-by":"crossref","unstructured":"A. Sahai, B. Waters, How to use indistinguishability obfuscation: deniable encryption, and more, in Symposium on Theory of Computing, STOC (2014), pp. 475\u2013484","DOI":"10.1145\/2591796.2591825"},{"issue":"11","key":"9431_CR91","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"L.G. Valiant, A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"9431_CR92","doi-asserted-by":"crossref","unstructured":"H. Wee, D. Wichs, Candidate obfuscation via oblivious LWE sampling, in EUROCRYPT (3), volume 12698 of Lecture Notes in Computer Science (Springer, 2021), pp. 127\u2013156","DOI":"10.1007\/978-3-030-77883-5_5"},{"key":"9431_CR93","unstructured":"R.R. Williams, Strong ETH breaks with merlin and arthur: Short non-interactive proofs of batch evaluation, in 31st Conference on Computational Complexity, CCC (2016), pp. 2:1\u20132:17"},{"key":"9431_CR94","doi-asserted-by":"crossref","unstructured":"J. Zimmerman, How to obfuscate programs directly, in Advances in Cryptology - EUROCRYPT (2015), pp. 439\u2013467","DOI":"10.1007\/978-3-662-46803-6_15"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09431-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-022-09431-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09431-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T18:20:47Z","timestamp":1658773247000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-022-09431-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":94,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["9431"],"URL":"https:\/\/doi.org\/10.1007\/s00145-022-09431-5","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"21 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"21"}}