{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:52:45Z","timestamp":1775281965968,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319705026","type":"print"},{"value":"9783319705033","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-70503-3_25","type":"book-chapter","created":{"date-parts":[[2017,11,4]],"date-time":"2017-11-04T02:43:27Z","timestamp":1509763407000},"page":"747-776","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Can PPAD Hardness be Based on Standard Cryptographic Assumptions?"],"prefix":"10.1007","author":[{"given":"Alon","family":"Rosen","sequence":"first","affiliation":[]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[]},{"given":"Ido","family":"Shahaf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,5]]},"reference":[{"key":"25_CR1","unstructured":"Abbot, T., Kane, D., Valiant, P.: On algorithms for Nash equilibria (2004). http:\/\/web.mit.edu\/tabbott\/Public\/final.pdf"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Asharov, G., Segev, G.: Limits on the power of indistinguishability obfuscation and functional encryption. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp. 191\u2013209 (2015)","DOI":"10.1109\/FOCS.2015.21"},{"key":"25_CR3","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"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44647-8_1","volume-title":"Advances in Cryptology \u2014 CRYPTO 2001","author":"B Barak","year":"2001","unstructured":"Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1\u201318. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44647-8_1"},{"issue":"2","key":"25_CR5","doi-asserted-by":"publisher","first-page":"6","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 (2012)","journal-title":"J. ACM"},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Merkle puzzles are optimal - an O(n$${}^{2}$$)-query attack on any key exchange from a random oracle. In: Advances in Cryptology - CRYPTO 2009, pp. 374\u2013390 (2009)","DOI":"10.1007\/978-3-642-03356-8_22"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Beame, P., Cook, S.A., Edmonds, J., Impagliazzo, R., Pitassi, T.: The relative complexity of NP search problems. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 303\u2013314 (1995)","DOI":"10.1145\/225058.225147"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Paneth, O., Rosen, A.: On the cryptographic hardness of finding a Nash equilibrium. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp. 1480\u20131498 (2015)","DOI":"10.1109\/FOCS.2015.94"},{"key":"25_CR9","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. 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":"25_CR10","unstructured":"Brakerski, Z., Gentry, C., Halevi, S., Lepoint, T., Sahai, A., Tibouchi, M.: Cryptanalysis of the quadratic zero-testing of GGH. Cryptology ePrint Archive, Report 2015\/845 (2015)"},{"issue":"3","key":"25_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 1\u201357 (2009)","journal-title":"J. ACM"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Fouque, P.-A., Lee, C., Minaud, B., Ryu, H.: Cryptanalysis of the new CLT multilinear map over the integers. Cryptology ePrint Archive, Report 2016\/135 (2016)","DOI":"10.1007\/978-3-662-49890-3_20"},{"key":"25_CR13","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":"25_CR14","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Jeong, J., Lee, C.: 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"},{"key":"25_CR15","unstructured":"Cheon, J.H., Lee, C., Ryu, H.: Cryptanalysis of the new CLT multilinear maps. Cryptology ePrint Archive, Report 2015\/934 (2015)"},{"issue":"2","key":"25_CR16","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1997.2646","volume":"137","author":"SA Cook","year":"1997","unstructured":"Cook, S.A., Impagliazzo, R., Yamakami, T.: A tight relationship between generic oracles and type-2 complexity theory. Inf. Comput. 137(2), 159\u2013170 (1997)","journal-title":"Inf. Comput."},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Coron, J., Gentry, C., Halevi, S., Lepoint, T., Maji, H.K., Miles, E., Raykova, M., Sahai, A., Tibouchi, M.: Zeroizing without low-level zeroes: new MMAP attacks and their limitations. In: Advances in Cryptology - CRYPTO 2015, pp. 247\u2013266 (2015)","DOI":"10.1007\/978-3-662-47989-6_12"},{"issue":"1","key":"25_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"key":"25_CR19","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: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 40\u201349 (2013)","DOI":"10.1109\/FOCS.2013.13"},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/978-3-662-53008-5_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"S Garg","year":"2016","unstructured":"Garg, S., Pandey, O., Srinivasan, A.: Revisiting the cryptographic hardness of finding a Nash equilibrium. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 579\u2013604. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53008-5_20"},{"key":"25_CR21","unstructured":"Goldreich, O.: On security preserving reductions - revised terminology. Cryptology ePrint Archive, Report 2000\/001 (2000)"},{"key":"25_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography \u2013 Volume 1: Basic Techniques","author":"O Goldreich","year":"2001","unstructured":"Goldreich, O.: Foundations of Cryptography \u2013 Volume 1: Basic Techniques. Cambridge University Press, Cambridge (2001)"},{"issue":"1","key":"25_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/130938438","volume":"44","author":"I Haitner","year":"2015","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193\u2013242 (2015)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"25_CR24","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0885-064X(89)90017-4","volume":"5","author":"MD Hirsch","year":"1989","unstructured":"Hirsch, M.D., Papadimitriou, C.H., Vavasis, S.A.: Exponential lower bounds for finding brouwer fix points. J. Complex. 5(4), 379\u2013416 (1989)","journal-title":"J. Complex."},{"key":"25_CR25","unstructured":"Hu, Y., Jia, H.: Cryptanalysis of GGH map. Cryptology ePrint Archive, Report 2015\/301 (2015)"},{"key":"25_CR26","unstructured":"Hub\u00e1cek, P., Naor, M., Yogev, E.: The journey from NP to TFNP hardness. In: Proceedings of the 8th Innovations in Theoretical Computer Science Conference (2017)"},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 44\u201361 (1989)","DOI":"10.1145\/73007.73012"},{"key":"25_CR28","doi-asserted-by":"crossref","DOI":"10.1515\/9780691206844","volume-title":"Pseudorandomness and Cryptographic Applications","author":"M Luby","year":"1996","unstructured":"Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton University Press, Princeton (1996)"},{"key":"25_CR29","doi-asserted-by":"crossref","unstructured":"Miles, E., Sahai, A., Zhandry, M.: Annihilation attacks for multilinear maps: cryptanalysis of indistinguishability obfuscation over GGH13. Cryptology ePrint Archive, Report 2016\/147 (2016)","DOI":"10.1007\/978-3-662-53008-5_22"},{"key":"25_CR30","unstructured":"Minaud, B., Fouque, P.-A.: Cryptanalysis of the new multilinear map over the integers. Cryptology ePrint Archive, Report 2015\/941 (2015)"},{"issue":"3","key":"25_CR31","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24638-1_1","volume-title":"Theory of Cryptography","author":"O Reingold","year":"2004","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1\u201320. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24638-1_1"},{"key":"25_CR33","doi-asserted-by":"crossref","unstructured":"Rosen, A., Segev, G., Shahaf, I.: Can PPAD hardness be based on standard cryptographic assumptions? Cryptology ePrint Archive, Report 2016\/375 (2016)","DOI":"10.1007\/978-3-319-70503-3_25"},{"key":"25_CR34","unstructured":"Rudich, S.: Limits on the provable consequences of one-way functions. Ph.D. thesis, EECS Department, University of California, Berkeley (1988)"},{"key":"25_CR35","doi-asserted-by":"crossref","unstructured":"Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 475\u2013484 (2014)","DOI":"10.1145\/2591796.2591825"},{"key":"25_CR36","doi-asserted-by":"crossref","unstructured":"Savani, R., von Stengel, B.: Exponentially many steps for finding a Nash equilibrium in a bimatrix game. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 258\u2013267 (2004)","DOI":"10.1109\/FOCS.2004.28"},{"key":"25_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 1998","author":"DR Simon","year":"1998","unstructured":"Simon, D.R.: Finding collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334\u2013345. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054137"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-70503-3_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T21:25:40Z","timestamp":1750973140000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-70503-3_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319705026","9783319705033"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-70503-3_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"5 November 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Baltimore","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":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 November 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 November 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.iacr.org\/workshops\/tcc2017\/","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"}]}}