{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,30]],"date-time":"2024-06-30T05:49:08Z","timestamp":1719726548101},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:00:00Z","timestamp":1560297600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:00:00Z","timestamp":1560297600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00145-019-09327-x","type":"journal-article","created":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T18:16:43Z","timestamp":1560363403000},"page":"406-458","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["From Minicrypt to Obfustopia via Private-Key Functional Encryption"],"prefix":"10.1007","volume":"33","author":[{"given":"Ilan","family":"Komargodski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"9327_CR1","unstructured":"S.\u00a0Agrawal, S.\u00a0Agrawal, S.\u00a0Badrinarayanan, A.\u00a0Kumarasubramanian, M.\u00a0Prabhakaran, A.\u00a0Sahai, Function private functional encryption and property preserving encryption: new definitions and positive results. Cryptology ePrint Archive, Report 2013\/744 (2013)"},{"key":"9327_CR2","unstructured":"P.\u00a0Ananth, D.\u00a0Boneh, S.\u00a0Garg, A.\u00a0Sahai, M.\u00a0Zhandry, Differing-inputs obfuscation and applications. Cryptology ePrint Archive, Report 2013\/689 (2013)"},{"key":"9327_CR3","unstructured":"P.\u00a0Ananth, Z.\u00a0Brakerski, G.\u00a0Segev, V.\u00a0Vaikuntanathan, From selective to adaptive security in functional encryption, in Advances in Cryptology\u2014CRYPTO \u201915 (2015), pp. 657\u2013677"},{"key":"9327_CR4","unstructured":"P.\u00a0Ananth, A.\u00a0Jain, Indistinguishability obfuscation from compact functional encryption, in Advances in Cryptology\u2014CRYPTO \u201915 (2015), pp. 308\u2013326"},{"key":"9327_CR5","unstructured":"P.\u00a0Ananth, A.\u00a0Jain, M.\u00a0Naor, A.\u00a0Sahai, E.\u00a0Yogev, Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption, in Advances in Cryptology\u2014CRYPTO \u201916 (2016), pp. 491\u2013520"},{"key":"9327_CR6","doi-asserted-by":"crossref","unstructured":"P.\u00a0Ananth, A.\u00a0Jain, A.\u00a0Sahai, Achieving compactness generically: indistinguishability obfuscation from non-compact functional encryption. Cryptology ePrint Archive, Report 2015\/730 (2015)","DOI":"10.1007\/978-3-662-47989-6_15"},{"key":"9327_CR7","unstructured":"T.\u00a0Abbot, D.\u00a0Kane, P.\u00a0Valiant, On algorithms for Nash equilibria (2004)"},{"issue":"6","key":"9327_CR8","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1137\/15M1034064","volume":"45","author":"G Asharov","year":"2016","unstructured":"G.\u00a0Asharov, G.\u00a0Segev, Limits on the power of indistinguishability obfuscation and functional encryption. SIAM J. Comput., 45(6), 2117\u20132176 (2016)","journal-title":"SIAM J. Comput."},{"key":"9327_CR9","unstructured":"E.\u00a0Boyle, K.\u00a0Chung, R.\u00a0Pass, On extractability obfuscation, in Proceedings of the 11th Theory of Cryptography Conference, TCC (2014), pp. 52\u201373"},{"key":"9327_CR10","unstructured":"Z.\u00a0Brakerski, C.\u00a0Gentry, S.\u00a0Halevi, T.\u00a0Lepoint, A.\u00a0Sahai, M.\u00a0Tibouchi, Cryptanalysis of the quadratic zero-testing of GGH. Cryptology ePrint Archive, Report 2015\/845 (2015)"},{"issue":"2","key":"9327_CR11","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/2160158.2160159","volume":"59","author":"B Barak","year":"2012","unstructured":"B.\u00a0Barak, O.\u00a0Goldreich, R.\u00a0Impagliazzo, S.\u00a0Rudich, A.\u00a0Sahai, S.\u00a0P. Vadhan, K.\u00a0Yang, On the (im)possibility of obfuscating programs. J. ACM, 59(2), 6 (2012)","journal-title":"J. ACM"},{"key":"9327_CR12","unstructured":"E.\u00a0Boyle, S.\u00a0Goldwasser, I.\u00a0Ivan, Functional signatures and pseudorandom functions, in Proceedings of the 17th International Conference on Practice and Theory in Public-Key Cryptography (2014), pp. 501\u2013519"},{"issue":"2","key":"9327_CR13","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/s00145-017-9261-0","volume":"31","author":"Z Brakerski","year":"2018","unstructured":"Z.\u00a0Brakerski, I.\u00a0Komargodski, G.\u00a0Segev, Multi-input functional encryption in the private-key setting: stronger security from weaker assumptions. J. Cryptol., 31(2), 434\u2013520 (2018)","journal-title":"J. Cryptol."},{"key":"9327_CR14","unstructured":"D.\u00a0Boneh, K.\u00a0Lewi, M.\u00a0Raykova, A.\u00a0Sahai, M.\u00a0Zhandry, J.\u00a0Zimmerman, Semantically secure order-revealing encryption: Multi-input functional encryption without obfuscation, in Advances in Cryptology\u2014EUROCRYPT \u201915 (2015), pp. 563\u2013594"},{"key":"9327_CR15","unstructured":"N.\u00a0Bitansky, R.\u00a0Nishimaki, A.\u00a0Passel\u00e8gue, D.\u00a0Wichs, From Cryptomania to Obfustopia through secret-key functional encryption, in Theory of Cryptography\u201414th International Conference, TCC 2016-B (2016), pp. 391\u2013418"},{"key":"9327_CR16","unstructured":"N.\u00a0Bitansky, O.\u00a0Paneth, A.\u00a0Rosen, On the cryptographic hardness of finding a Nash equilibrium, in Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (2015), pp. 1480\u20131498"},{"key":"9327_CR17","unstructured":"D.\u00a0Boneh, A.\u00a0Raghunathan, G.\u00a0Segev, Function-private identity-based encryption: hiding the function in functional encryption, in Advances in Cryptology\u2014CRYPTO \u201913 (2013), pp. 461\u2013478"},{"key":"9327_CR18","unstructured":"D.\u00a0Boneh, A.\u00a0Raghunathan, G.\u00a0Segev, Function-private subspace-membership encryption and its applications, in Advances in Cryptology\u2014ASIACRYPT \u201913 (2013), pp. 255\u2013275"},{"key":"9327_CR19","unstructured":"Z.\u00a0Brakerski, G.\u00a0Segev, Function-private functional encryption in the private-key setting, in Proceedings of the 12th Theory of Cryptography Conference, TCC (2015), pp. 306\u2013324"},{"key":"9327_CR20","unstructured":"D.\u00a0Boneh, A.\u00a0Sahai, B.\u00a0Waters, Functional encryption: definitions and challenges, in Proceedings of the 8th Theory of Cryptography Conference, TCC (2011), pp. 253\u2013273"},{"issue":"11","key":"9327_CR21","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/2366316.2366333","volume":"55","author":"D Boneh","year":"2012","unstructured":"D.\u00a0Boneh, A.\u00a0Sahai, B.\u00a0Waters, Functional encryption: a new vision for public-key cryptography. Commun. ACM, 55(11), 56\u201364 (2012)","journal-title":"Commun. ACM"},{"key":"9327_CR22","unstructured":"N.\u00a0Bitansky, V.\u00a0Vaikuntanathan, Indistinguishability obfuscation from functional encryption, in Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (2015), pp. 171\u2013190"},{"key":"9327_CR23","unstructured":"D.\u00a0Boneh, B.\u00a0Waters, Constrained pseudorandom functions and their applications, in Advances in Cryptology\u2014ASIACRYPT \u201913 (2013), pp. 280\u2013300"},{"issue":"3","key":"9327_CR24","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"X.\u00a0Chen, X.\u00a0Deng, S.\u00a0Teng, Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3), 14 (2009)","journal-title":"J. ACM"},{"key":"9327_CR25","unstructured":"J.H. Cheon, P.\u00a0Fouque, C.\u00a0Lee, B.\u00a0Minaud, H.\u00a0Ryu, Cryptanalysis of the new CLT multilinear map over the integers, in Advances in Cryptology\u2014EUROCRYPT (2016), pp. 509\u2013536"},{"key":"9327_CR26","unstructured":"J.\u00a0Coron, C.\u00a0Gentry, S.\u00a0Halevi, T.\u00a0Lepoint, H.K. Maji, E.\u00a0Miles, M.\u00a0Raykova, A.\u00a0Sahai, M.\u00a0Tibouchi, Zeroizing without low-level zeroes: new MMAP attacks and their limitations, in Advances in Cryptology\u2014CRYPTO \u201915 (2015), pp. 247\u2013266"},{"key":"9327_CR27","unstructured":"J.H. Cheon, K.\u00a0Han, C.\u00a0Lee, H.\u00a0Ryu, D.\u00a0Stehl\u00e9, Cryptanalysis of the multilinear map over the integers, in Advances in Cryptology\u2014EUROCRYPT \u201915 (2015), pp. 3\u201312"},{"key":"9327_CR28","doi-asserted-by":"crossref","unstructured":"J.H. Cheon, J.\u00a0Jeong, C.\u00a0Lee, An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero. Cryptology ePrint Archive, Report 2016\/139 (2016)","DOI":"10.1112\/S1461157016000371"},{"issue":"2","key":"9327_CR29","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1145\/1461928.1461951","volume":"52","author":"C Daskalakis","year":"2009","unstructured":"C.\u00a0Daskalakis, P.\u00a0W. Goldberg, C.H. Papadimitriou, The complexity of computing a Nash equilibrium. Commun. ACM, 52(2), 89\u201397 (2009)","journal-title":"Commun. ACM"},{"issue":"1","key":"9327_CR30","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C Daskalakis","year":"2009","unstructured":"C.\u00a0Daskalakis, P.W. Goldberg, C.H. Papadimitriou, The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1), 195\u2014259 (2009)","journal-title":"SIAM J. Comput."},{"key":"9327_CR31","unstructured":"C.\u00a0Daskalakis, C.H. Papadimitriou, Continuous local search, in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (2011), pp. 790\u2013804"},{"key":"9327_CR32","unstructured":"S.\u00a0Goldwasser, S.D. Gordon, V.\u00a0Goyal, A.\u00a0Jain, J.\u00a0Katz, F.-H. Liu, A.\u00a0Sahai, E.\u00a0Shi, H.-S. Zhou, Multi-input functional encryption, in Advances in Cryptology\u2014EUROCRYPT \u201914 (2014), pp. 578\u2013602"},{"key":"9327_CR33","unstructured":"S.\u00a0Garg, C.\u00a0Gentry, S.\u00a0Halevi, M.\u00a0Raykova, A.\u00a0Sahai, B.\u00a0Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits, in Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (2013), pp. 40\u201349"},{"key":"9327_CR34","unstructured":"S.\u00a0Garg, C.\u00a0Gentry, S.\u00a0Halevi, M.\u00a0Zhandry, Functional encryption without obfuscation, in Proceedings of the 13th Theory of Cryptography Conference, TCC (2016), pp. 480\u2013511"},{"issue":"4","key":"9327_CR35","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"O.\u00a0Goldreich, S.\u00a0Goldwasser, S.\u00a0Micali, How to construct random functions. J. ACM, 33(4), 792-807 (1986)","journal-title":"J. ACM"},{"key":"9327_CR36","unstructured":"S.\u00a0Goldwasser, Y.\u00a0Kalai, R.A. Popa, V.\u00a0Vaikuntanathan, N.\u00a0Zeldovich, Reusable garbled circuits and succinct functional encryption, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing (2013), pp. 555\u2013564"},{"key":"9327_CR37","unstructured":"S.\u00a0Garg, O.\u00a0Pandey, A.\u00a0Srinivasan, Revisiting the cryptographic hardness of finding a Nash equilibrium, in Advances in Cryptology\u2014CRYPTO \u201916 (2016), pp. 579\u2013604"},{"key":"9327_CR38","unstructured":"S.\u00a0Garg, A.\u00a0Srinivasan, Single-key to multi-key functional encryption with polynomial loss, in Theory of Cryptography\u201414th International Conference, TCC (2016), pp. 419\u2013442"},{"key":"9327_CR39","unstructured":"S.\u00a0Gorbunov, V.\u00a0Vaikuntanathan, H.\u00a0Wee, Functional encryption with bounded collusions via multi-party computation, in Advances in Cryptology\u2014CRYPTO \u201912 (2012), pp. 162\u2013179"},{"key":"9327_CR40","unstructured":"Y.\u00a0Hu, H.\u00a0Jia, Cryptanalysis of GGH map, in Advances in Cryptology\u2014EUROCRYPT (2016), pp. 537\u2013565"},{"key":"9327_CR41","unstructured":"P.\u00a0Hub\u00e1cek, E.\u00a0Yogev, Hardness of continuous local search: Query complexity and cryptographic lower bounds, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2017), pp. 1352\u20131371"},{"key":"9327_CR42","unstructured":"R.\u00a0Impagliazzo, A personal view of average-case complexity, in Proceedings of the 10th Annual Structure in Complexity Theory Conference (1995), pp. 134\u2013147"},{"key":"9327_CR43","unstructured":"I.\u00a0Komargodski, T.\u00a0Moran, M.\u00a0Naor, R.\u00a0Pass, A.\u00a0Rosen, E.\u00a0Yogev, One-way functions and (im)perfect obfuscation, in Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (2014), pp. 374\u2013383"},{"key":"9327_CR44","unstructured":"F.\u00a0Kitagawa, R.\u00a0Nishimaki, K.\u00a0Tanaka, Obfustopia built on secret-key functional encryption, in Advances in Cryptology\u2014EUROCRYPT (2018), pp. 603\u2013648"},{"key":"9327_CR45","unstructured":"A.\u00a0Kiayias, S.\u00a0Papadopoulos, N.\u00a0Triandopoulos, T.\u00a0Zacharias, Delegatable pseudorandom functions and applications, in Proceedings of the 20th Annual ACM Conference on Computer and Communications Security (2013), pp. 669\u2013684"},{"issue":"1","key":"9327_CR46","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s00145-016-9250-8","volume":"31","author":"I Komargodski","year":"2018","unstructured":"I.\u00a0Komargodski, G.\u00a0Segev, E.\u00a0Yogev, Functional encryption for randomized functionalities in the private-key setting from minimal assumptions. J. Cryptol., 31(1), 60\u2013100 (2018)","journal-title":"J. Cryptol."},{"key":"9327_CR47","unstructured":"B.\u00a0Li, D.\u00a0Micciancio, Compactness vs collusion resistance in functional encryption, in Theory of Cryptography\u201414th International Conference, TCC (2016), pp. 443\u2013468"},{"key":"9327_CR48","unstructured":"E.\u00a0Miles, A.\u00a0Sahai, M.\u00a0Zhandry, Annihilation attacks for multilinear maps: cryptanalysis of indistinguishability obfuscation over GGH13, in Advances in Cryptology\u2014CRYPTO (2016), pp. 629\u2013658"},{"key":"9327_CR49","unstructured":"A.\u00a0O\u2019Neill, Definitional issues in functional encryption. Cryptology ePrint Archive, Report 2010\/556 (2010)"},{"issue":"3","key":"9327_CR50","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"C.H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3), 498-532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9327_CR51","unstructured":"E.\u00a0Shen, E.\u00a0Shi, B.\u00a0Waters, Predicate privacy in encryption systems, in Proceedings of the 6th Theory of Cryptography Conference, TCC (2009), pp. 457\u2013473"},{"key":"9327_CR52","unstructured":"A.\u00a0Sahai, B.\u00a0Waters, Slides on functional encryption (2008). \nhttp:\/\/www.cs.utexas.edu\/~bwaters\/presentations\/files\/functional.ppt"},{"key":"9327_CR53","unstructured":"A.\u00a0Sahai, B.\u00a0Waters, How to use indistinguishability obfuscation: deniable encryption, and more, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (2014), pp. 475\u2013484"},{"key":"9327_CR54","unstructured":"B.\u00a0Waters, A punctured programming approach to adaptively secure functional encryption, in Advances in Cryptology\u2014CRYPTO \u201915 (2015), pp. 678\u2013697"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09327-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-019-09327-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09327-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,10]],"date-time":"2020-06-10T23:23:11Z","timestamp":1591831391000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-019-09327-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,12]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9327"],"URL":"https:\/\/doi.org\/10.1007\/s00145-019-09327-x","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,12]]},"assertion":[{"value":"9 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}