{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:15:50Z","timestamp":1759335350453,"version":"3.41.0"},"publisher-location":"Cham","reference-count":73,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319968773"},{"type":"electronic","value":"9783319968780"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-96878-0_26","type":"book-chapter","created":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T12:53:57Z","timestamp":1532350437000},"page":"753-783","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Compressing Obfuscation"],"prefix":"10.1007","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Ephraim","sequence":"additional","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"}]}],"member":"297","published-online":{"date-parts":[[2018,7,24]]},"reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/978-3-662-53008-5_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"P Ananth","year":"2016","unstructured":"Ananth, P., Jain, A., Naor, M., Sahai, A., Yogev, E.: Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 491\u2013520. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53008-5_17"},{"key":"26_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-319-56620-7_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"P Ananth","year":"2017","unstructured":"Ananth, P., Jain, A., Sahai, A.: Robust transforming combiners from indistinguishability obfuscation to functional encryption. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 91\u2013121. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56620-7_4"},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-662-47989-6_15","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"P Ananth","year":"2015","unstructured":"Ananth, P., Jain, A.: Indistinguishability obfuscation from compact functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 308\u2013326. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_15"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-319-56620-7_6","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"P Ananth","year":"2017","unstructured":"Ananth, P., Sahai, A.: Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 152\u2013181. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56620-7_6"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Ananth, P.V., Gupta, D., Ishai, Y., Sahai, A.: Optimizing obfuscation: avoiding Barrington\u2019s theorem. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 646\u2013658 (2014)","DOI":"10.1145\/2660267.2660342"},{"issue":"4","key":"26_CR6","first-page":"319","volume":"2","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1987)","journal-title":"Mach. Learn."},{"key":"26_CR7","unstructured":"Apon, D., D\u00f6ttling, N., Garg, S., Mukherjee, P.: Cryptanalysis of indistinguishability obfuscations of circuits over GGH13. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pp. 38:1\u201338:16 (2017)"},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/978-3-662-46497-7_21","volume-title":"Theory of Cryptography","author":"B Applebaum","year":"2015","unstructured":"Applebaum, B., Brakerski, Z.: Obfuscating circuits via composite-order graded encoding. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 528\u2013556. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46497-7_21"},{"issue":"6","key":"26_CR9","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1137\/15M1034064","volume":"45","author":"G Asharov","year":"2016","unstructured":"Asharov, G., Segev, G.: Limits on the power of indistinguishability obfuscation and functional encryption. SIAM J. Comput. 45(6), 2117\u20132176 (2016)","journal-title":"SIAM J. Comput."},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/978-3-662-49099-0_19","volume-title":"Theory of Cryptography","author":"G Asharov","year":"2016","unstructured":"Asharov, G., Segev, G.: On constructing one-way permutations from indistinguishability obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 512\u2013541. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_19"},{"issue":"6","key":"26_CR11","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/0898-1221(81)90029-8","volume":"7","author":"C Asmuth","year":"1981","unstructured":"Asmuth, C., Blakley, G.: An efficient algorithm for constructing a cryptosystem which is harder to break than two other cryptosystems. Comput. Math. Appl. 7(6), 447\u2013450 (1981)","journal-title":"Comput. Math. Appl."},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Barak, B., Brakerski, Z., Komargodski, I., Kothari, P.K.: Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation). IACR Cryptology ePrint Archive 2017, 312 (2017)","DOI":"10.1007\/978-3-319-78375-8_21"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-642-55220-5_13","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"B Barak","year":"2014","unstructured":"Barak, B., Garg, S., Kalai, Y.T., Paneth, O., Sahai, A.: Protecting obfuscation against algebraic attacks. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 221\u2013238. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_13"},{"issue":"2","key":"26_CR14","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/2160158.2160159","volume":"59","author":"B Barak","year":"2012","unstructured":"Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6:1\u20136:48 (2012)","journal-title":"J. ACM"},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1007\/978-3-319-63688-7_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"N Bitansky","year":"2017","unstructured":"Bitansky, N., Degwekar, A., Vaikuntanathan, V.: Structure vs. hardness through the obfuscation lens. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 696\u2013723. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_23"},{"key":"26_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-56614-6_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"N Bitansky","year":"2017","unstructured":"Bitansky, N., Lin, H., Paneth, O.: On removing graded encodings from functional encryption. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Proceedings, Part II. LNCS, vol. 10211, pp. 3\u201329. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56614-6_1"},{"key":"26_CR17","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/978-3-662-53644-5_15","volume-title":"Theory of Cryptography","author":"Nir Bitansky","year":"2016","unstructured":"Bitansky, N., Nishimaki, R., Passel\u00e8gue, A., Wichs, D.: From cryptomania to obfustopia through secret-key functional encryption. In: Theory of Cryptography Conference, pp. 391\u2013418 (2016)"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-662-46497-7_16","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2015","unstructured":"Bitansky, N., Paneth, O.: ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 401\u2013427. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46497-7_16"},{"key":"26_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/978-3-662-49096-9_20","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2016","unstructured":"Bitansky, N., Paneth, O., Wichs, D.: Perfect structure on the edge of chaos - trapdoor permutations from indistinguishability obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 474\u2013502. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49096-9_20"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Vaikuntanathan, V.: Indistinguishability obfuscation from functional encryption. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pp. 171\u2013190 (2015)","DOI":"10.1109\/FOCS.2015.20"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-662-49096-9_4","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2016","unstructured":"Bitansky, N., Vaikuntanathan, V.: Indistinguishability obfuscation: from approximate to exact. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 67\u201395. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49096-9_4"},{"key":"26_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/978-3-319-56614-6_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"N Bitansky","year":"2017","unstructured":"Bitansky, N., Vaikuntanathan, V.: A note on perfect correctness by derandomization. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 592\u2013606. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56614-6_20"},{"key":"26_CR23","unstructured":"Boneh, D., Wu, D.J., Zimmerman, J.: Immunizing multilinear maps against zeroizing attacks. IACR Cryptology ePrint Archive 2014, 930 (2014)"},{"key":"26_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-662-53008-5_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"Z Brakerski","year":"2016","unstructured":"Brakerski, Z., Brzuska, C., Fleischhacker, N.: On statistically secure obfuscation with approximate correctness. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 551\u2013578. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53008-5_19"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Jain, A., Komargodski, I., Passel\u00e8gue, A., Wichs, D.: Non-trivial witness encryption and null-iO from standard assumptions. IACR Cryptology ePrint Archive 2017, 874 (2017)","DOI":"10.1007\/978-3-319-98113-0_23"},{"key":"26_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-642-19571-6_34","volume-title":"Theory of Cryptography","author":"Z Brakerski","year":"2011","unstructured":"Brakerski, Z., Katz, J., Segev, G., Yerukhimovich, A.: Limits on the power of zero-knowledge proofs in cryptographic constructions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 559\u2013578. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19571-6_34"},{"key":"26_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-54242-8_1","volume-title":"Theory of Cryptography","author":"Z Brakerski","year":"2014","unstructured":"Brakerski, Z., Rothblum, G.N.: Virtual black-box obfuscation for all circuits via generic graded encoding. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 1\u201325. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_1"},{"issue":"4","key":"26_CR28","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"NH Bshouty","year":"1996","unstructured":"Bshouty, N.H., Tamon, C.: On the fourier spectrum of monotone functions. J. ACM 43(4), 747\u2013770 (1996)","journal-title":"J. ACM"},{"key":"26_CR29","unstructured":"Carmosino, M.L., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Learning algorithms from natural proofs. In: 31st Conference on Computational Complexity, CCC 2016, vol. 50, pp. 10:1\u201310:24 (2016)"},{"key":"26_CR30","unstructured":"Carmosino, M.L., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Agnostic learning from tolerant natural proofs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2017, vol. 81, pp. 35:1\u201335:19 (2017)"},{"issue":"2","key":"26_CR31","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00037-015-0100-0","volume":"24","author":"R Chen","year":"2015","unstructured":"Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R., Zuckerman, D.: Mining circuit lower bound proofs for meta-algorithms. Comput. Complex. 24(2), 333\u2013392 (2015)","journal-title":"Comput. Complex."},{"key":"26_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-319-56617-7_10","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"Y Chen","year":"2017","unstructured":"Chen, Y., Gentry, C., Halevi, S.: Cryptanalyses of candidate branching program obfuscators. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 278\u2013307. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56617-7_10"},{"key":"26_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-46800-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2015","author":"JH Cheon","year":"2015","unstructured":"Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehl\u00e9, D.: Cryptanalysis of the multilinear map over the integers. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 3\u201312. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46800-5_1"},{"key":"26_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/978-3-642-40041-4_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"J-S Coron","year":"2013","unstructured":"Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 476\u2013493. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_26"},{"key":"26_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-662-47989-6_13","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"J-S Coron","year":"2015","unstructured":"Coron, J.-S., Lepoint, T., Tibouchi, M.: New multilinear maps over the integers. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 267\u2013286. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_13"},{"key":"26_CR36","doi-asserted-by":"crossref","unstructured":"Diffie, W., Hellman, M.E.: Multiuser cryptographic techniques. In: American Federation of Information Processing Societies, pp. 109\u2013112 (1976)","DOI":"10.1145\/1499799.1499815"},{"key":"26_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-662-53008-5_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"M Fischlin","year":"2016","unstructured":"Fischlin, M., Herzberg, A., Bin-Noon, H., Shulman, H.: Obfuscation combiners. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 521\u2013550. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53008-5_18"},{"key":"26_CR38","doi-asserted-by":"crossref","unstructured":"Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pp. 40\u201349. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.13"},{"key":"26_CR39","doi-asserted-by":"crossref","unstructured":"Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: Symposium on Theory of Computing Conference, STOC 2013, pp. 467\u2013476 (2013)","DOI":"10.1145\/2488608.2488667"},{"key":"26_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/978-3-319-63688-7_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"S Garg","year":"2017","unstructured":"Garg, S., Mahmoody, M., Mohammed, A.: Lower bounds on obfuscation from all-or-nothing encryption primitives. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 661\u2013695. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_22"},{"key":"26_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-319-70500-2_4","volume-title":"Theory of Cryptography","author":"S Garg","year":"2017","unstructured":"Garg, S., Mahmoody, M., Mohammed, A.: When does functional encryption imply obfuscation? In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 82\u2013115. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70500-2_4"},{"key":"26_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/978-3-662-46497-7_20","volume-title":"Theory of Cryptography","author":"C Gentry","year":"2015","unstructured":"Gentry, C., Gorbunov, S., Halevi, S.: Graph-induced multilinear maps from lattices. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 498\u2013527. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46497-7_20"},{"key":"26_CR43","unstructured":"Gentry, C., Halevi, S., Maji, H.K., Sahai, A.: Zeroizing without zeroes: cryptanalyzing multilinear maps without encodings of zero. IACR Cryptology ePrint Archive 2014, 929 (2014)"},{"key":"26_CR44","doi-asserted-by":"crossref","unstructured":"Gentry, C., Lewko, A.B., Sahai, A., Waters, B.: Indistinguishability obfuscation from the multilinear subgroup elimination assumption. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pp. 151\u2013170 (2015)","DOI":"10.1109\/FOCS.2015.19"},{"key":"26_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/978-3-642-55220-5_32","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"S Goldwasser","year":"2014","unstructured":"Goldwasser, S., et al.: Multi-input functional encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 578\u2013602. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_32"},{"key":"26_CR46","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: Symposium on Theory of Computing Conference, STOC 2013, pp. 555\u2013564 (2013)","DOI":"10.1145\/2488608.2488678"},{"key":"26_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-70936-7_11","volume-title":"Theory of Cryptography","author":"S Goldwasser","year":"2007","unstructured":"Goldwasser, S., Rothblum, G.N.: On best-possible obfuscation. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 194\u2013213. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-70936-7_11"},{"key":"26_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/11426639_6","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"D Harnik","year":"2005","unstructured":"Harnik, D., Kilian, J., Naor, M., Reingold, O., Rosen, A.: On robust combiners for oblivious transfer and other primitives. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 96\u2013113. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11426639_6"},{"key":"26_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-540-30574-3_13","volume-title":"Topics in Cryptology \u2013 CT-RSA 2005","author":"A Herzberg","year":"2005","unstructured":"Herzberg, A.: On tolerant cryptographic constructions. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 172\u2013190. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-30574-3_13"},{"issue":"2","key":"26_CR50","doi-asserted-by":"publisher","first-page":"159","DOI":"10.3233\/JCS-2009-0336","volume":"17","author":"A Herzberg","year":"2009","unstructured":"Herzberg, A.: Folklore, practice and theory of robust combiners. J. Comput. Secur. 17(2), 159\u2013189 (2009)","journal-title":"J. Comput. Secur."},{"key":"26_CR51","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 44\u201361. ACM (1989)","DOI":"10.1145\/73007.73012"},{"issue":"2\u20133","key":"26_CR52","first-page":"115","volume":"17","author":"MJ Kearns","year":"1994","unstructured":"Kearns, M.J., Schapire, R.E., Sellie, L.: Toward efficient agnostic learning. Mach. Learn. 17(2\u20133), 115\u2013141 (1994)","journal-title":"Mach. Learn."},{"key":"26_CR53","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Moran, T., Naor, M., Pass, R., Rosen, A., Yogev, E.: One-way functions and (im)perfect obfuscation. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 374\u2013383 (2014)","DOI":"10.1109\/FOCS.2014.47"},{"issue":"4","key":"26_CR54","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"LA Levin","year":"1987","unstructured":"Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7(4), 357\u2013363 (1987)","journal-title":"Combinatorica"},{"key":"26_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-662-49890-3_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"H Lin","year":"2016","unstructured":"Lin, H.: Indistinguishability obfuscation from constant-degree graded encoding schemes. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 28\u201357. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49890-3_2"},{"key":"26_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/978-3-319-63688-7_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"H Lin","year":"2017","unstructured":"Lin, H.: Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 599\u2013629. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_20"},{"key":"26_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-662-49387-8_17","volume-title":"Public-Key Cryptography \u2013 PKC 2016","author":"H Lin","year":"2016","unstructured":"Lin, H., Pass, R., Seth, K., Telang, S.: Indistinguishability obfuscation with non-trivial efficiency. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9615, pp. 447\u2013462. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49387-8_17"},{"key":"26_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-662-49096-9_5","volume-title":"Theory of Cryptography","author":"H Lin","year":"2016","unstructured":"Lin, H., Pass, R., Seth, K., Telang, S.: Output-compressing randomized encodings and applications. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9562, pp. 96\u2013124. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49096-9_5"},{"key":"26_CR59","doi-asserted-by":"crossref","unstructured":"Lin, H., Vaikuntanathan, V.: 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 (2016)","DOI":"10.1109\/FOCS.2016.11"},{"key":"26_CR60","doi-asserted-by":"crossref","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. In: 30th Annual Symposium on Foundations of Computer Science, pp. 574\u2013579 (1989)","DOI":"10.1109\/SFCS.1989.63537"},{"key":"26_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-319-70500-2_6","volume-title":"Theory of Cryptography","author":"Q Liu","year":"2017","unstructured":"Liu, Q., Zhandry, M.: Decomposable obfuscation: a framework for building applications of obfuscation from polynomial hardness. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 138\u2013169. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70500-2_6"},{"key":"26_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-319-70500-2_5","volume-title":"Theory of Cryptography","author":"A Lombardi","year":"2017","unstructured":"Lombardi, A., Vaikuntanathan, V.: Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 119\u2013137. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70500-2_5"},{"key":"26_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-662-49096-9_3","volume-title":"Theory of Cryptography","author":"M Mahmoody","year":"2016","unstructured":"Mahmoody, M., Mohammed, A., Nematihaji, S., Pass, R., Shelat, A.: Lower bounds on assumptions behind indistinguishability obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9562, pp. 49\u201366. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49096-9_3"},{"key":"26_CR64","doi-asserted-by":"crossref","unstructured":"Mahmoody, M., Xiao, D.: On the power of randomized reductions and the checkability of SAT. In: CCC 2010, pp. 64\u201375. IEEE Computer Society (2010)","DOI":"10.1109\/CCC.2010.16"},{"key":"26_CR65","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-30576-7_1","volume-title":"Theory of Cryptography","author":"S Micali","year":"2005","unstructured":"Micali, S., Peikert, C., Sudan, M., Wilson, D.A.: Optimal error correction against computationally bounded noise. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 1\u201316. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-30576-7_1"},{"key":"26_CR66","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/978-3-662-53008-5_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"E Miles","year":"2016","unstructured":"Miles, E., Sahai, A., Zhandry, M.: Annihilation attacks for multilinear maps: cryptanalysis of indistinguishability obfuscation over GGH13. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 629\u2013658. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53008-5_22"},{"issue":"1","key":"26_CR67","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jcss.1999.1664","volume":"60","author":"T Okamoto","year":"2000","unstructured":"Okamoto, T.: On relationships between statistical zero-knowledge proofs. J. Comput. Syst. Sci. 60(1), 47\u2013108 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-662-44371-2_28","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"R Pass","year":"2014","unstructured":"Pass, R., Seth, K., Telang, S.: Indistinguishability obfuscation from semantically-secure multilinear encodings. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 500\u2013517. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44371-2_28"},{"issue":"1","key":"26_CR69","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"AA Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24\u201335 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR70","doi-asserted-by":"crossref","unstructured":"Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Symposium on Theory of Computing, STOC 2014, pp. 475\u2013484 (2014)","DOI":"10.1145\/2591796.2591825"},{"issue":"11","key":"26_CR71","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"26_CR72","unstructured":"Williams, R.R.: Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. In: CCC, vol. 50, pp. 2:1\u20132:17 (2016)"},{"key":"26_CR73","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/978-3-662-46803-6_15","volume-title":"Advances in Cryptology - EUROCRYPT 2015","author":"J Zimmerman","year":"2015","unstructured":"Zimmerman, J.: How to obfuscate programs directly. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 439\u2013467. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46803-6_15"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2018"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-96878-0_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T23:35:10Z","timestamp":1751758510000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-96878-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319968773","9783319968780"],"references-count":73,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96878-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"24 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 August 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"38","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}