{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T14:26:04Z","timestamp":1698157564519},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021,1]]},"DOI":"10.1007\/s00145-020-09369-6","type":"journal-article","created":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T21:28:55Z","timestamp":1610486935000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Can PPAD Hardness be Based on Standard Cryptographic Assumptions?"],"prefix":"10.1007","volume":"34","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":[[2021,1,12]]},"reference":[{"key":"9369_CR1","unstructured":"T.\u00a0Abbot, D.\u00a0Kane, P.\u00a0Valiant, On algorithms for Nash equilibria. Unpublished manuscript. http:\/\/web.mit.edu\/tabbott\/Public\/final.pdf (2004)"},{"key":"9369_CR2","doi-asserted-by":"crossref","unstructured":"G.\u00a0Asharov, G.\u00a0Segev, 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":"9369_CR3","doi-asserted-by":"crossref","unstructured":"G.\u00a0Asharov, G.\u00a0Segev, On constructing one-way permutations from indistinguishability obfuscation, in Proceedings of the 13th Theory of Cryptography Conference, pp. 512\u2013541 (2016)","DOI":"10.1007\/978-3-662-49099-0_19"},{"key":"9369_CR4","doi-asserted-by":"crossref","unstructured":"P.\u00a0Beame, S.A. Cook, J.\u00a0Edmonds, R.\u00a0Impagliazzo, T.\u00a0Pitassi, 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":"9369_CR5","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)"},{"key":"9369_CR6","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, O.\u00a0Goldreich, R.\u00a0Impagliazzo, S.\u00a0Rudich, A.\u00a0Sahai, S.P. Vadhan, K.\u00a0Yang, On the (im)possibility of obfuscating programs, in Advances in Cryptology\u2014CRYPTO\u201901, pp. 1\u201318 (2001)","DOI":"10.1007\/3-540-44647-8_1"},{"key":"9369_CR7","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, O.\u00a0Goldreich, R.\u00a0Impagliazzo, S.\u00a0Rudich, A.\u00a0Sahai, S.P. Vadhan, K.\u00a0Yang, On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012)","DOI":"10.1145\/2160158.2160159"},{"key":"9369_CR8","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, M.\u00a0Mahmoody-Ghidary, Merkle puzzles are optimal\u2014an O(n$${}^{2}$$)-query attack on any key exchange from a random oracle, in Advances in Cryptology\u2014CRYPTO\u201909, pp. 374\u2013390 (2009)","DOI":"10.1007\/978-3-642-03356-8_22"},{"key":"9369_CR9","doi-asserted-by":"crossref","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, pp. 1480\u20131498 (2015)","DOI":"10.1109\/FOCS.2015.94"},{"key":"9369_CR10","doi-asserted-by":"crossref","unstructured":"N.\u00a0Bitansky, O.\u00a0Paneth, D.\u00a0Wichs, Perfect structure on the edge of chaos\u2014trapdoor permutations from indistinguishability obfuscation, in Proceedings of the 13th Theory of Cryptography Conference, pp. 474\u2013502 (2016)","DOI":"10.1007\/978-3-662-49096-9_20"},{"key":"9369_CR11","doi-asserted-by":"crossref","unstructured":"X.\u00a0Chen, X.\u00a0Deng, S.\u00a0Teng, Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3) (2009)","DOI":"10.1145\/1516512.1516516"},{"key":"9369_CR12","doi-asserted-by":"crossref","unstructured":"J.H. Cheon, P.-A. Fouque, C.\u00a0Lee, B.\u00a0Minaud, H.\u00a0Ryu, 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":"9369_CR13","doi-asserted-by":"crossref","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, pp. 247\u2013266 (2015)","DOI":"10.1007\/978-3-662-47989-6_12"},{"key":"9369_CR14","doi-asserted-by":"crossref","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, pp. 3\u201312 (2015)","DOI":"10.1007\/978-3-662-46800-5_1"},{"key":"9369_CR15","doi-asserted-by":"crossref","unstructured":"S.A. Cook, R.\u00a0Impagliazzo, T.\u00a0Yamakami, A tight relationship between generic oracles and type-2 complexity theory. Inf. Comput. 137(2), 159\u2013170 (1997)","DOI":"10.1006\/inco.1997.2646"},{"key":"9369_CR16","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"},{"key":"9369_CR17","unstructured":"J.H. Cheon, C.\u00a0Lee, H.\u00a0Ryu, Cryptanalysis of the new CLT multilinear maps. Cryptology ePrint Archive, Report 2015\/934 (2015)"},{"key":"9369_CR18","doi-asserted-by":"crossref","unstructured":"C.\u00a0Daskalakis, P.W. Goldberg, C.H. Papadimitriou, The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009)","DOI":"10.1137\/070699652"},{"key":"9369_CR19","doi-asserted-by":"crossref","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, pp. 40\u201349 (2013)","DOI":"10.1109\/FOCS.2013.13"},{"key":"9369_CR20","unstructured":"O.\u00a0Goldreich, On security preserving reductions\u2014revised terminology. Cryptology ePrint Archive, Report 2000\/001 (2000)"},{"key":"9369_CR21","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography\u2014Volume 1: Basic Techniques (Cambridge University Press, 2001)","DOI":"10.1017\/CBO9780511546891"},{"key":"9369_CR22","doi-asserted-by":"crossref","unstructured":"S.\u00a0Garg, O.\u00a0Pandey, A.\u00a0Srinivasan, Revisiting the cryptographic hardness of finding a Nash equilibrium, in Advances in Cryptology\u2013CRYPTO\u201916, pp. 579\u2013604 (2016)","DOI":"10.1007\/978-3-662-53008-5_20"},{"key":"9369_CR23","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, J.J. Hoch, O.\u00a0Reingold, G.\u00a0Segev, Finding collisions in interactive protocols\u2014tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193\u2013242 (2015)","DOI":"10.1137\/130938438"},{"key":"9369_CR24","unstructured":"Y.\u00a0Hu, H.\u00a0Jia, Cryptanalysis of GGH map. Cryptology ePrint Archive, Report 2015\/301 (2015)"},{"key":"9369_CR25","unstructured":"P.\u00a0Hub\u00e1cek, M.\u00a0Naor, E.\u00a0Yogev, The journey from NP to TFNP hardness, in Proceedings of the 8th Innovations in Theoretical Computer Science Conference (2017)"},{"key":"9369_CR26","doi-asserted-by":"crossref","unstructured":"M.D. Hirsch, C.H. Papadimitriou, S.A. Vavasis, Exponential lower bounds for finding brouwer fix points. J. Complex. 5(4), 379\u2013416 (1989)","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"9369_CR27","doi-asserted-by":"crossref","unstructured":"R.\u00a0Impagliazzo, S.\u00a0Rudich, 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":"9369_CR28","doi-asserted-by":"crossref","unstructured":"M.\u00a0Luby, Pseudorandomness and Cryptographic Applications (Princeton University Press, 1996)","DOI":"10.1515\/9780691206844"},{"key":"9369_CR29","unstructured":"B.\u00a0Minaud, P.-A. Fouque, Cryptanalysis of the new multilinear map over the integers. Cryptology ePrint Archive, Report 2015\/941 (2015)"},{"key":"9369_CR30","doi-asserted-by":"crossref","unstructured":"E.\u00a0Miles, A.\u00a0Sahai, M.\u00a0Zhandry, 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":"9369_CR31","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994)","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"9369_CR32","doi-asserted-by":"crossref","unstructured":"O.\u00a0Reingold, L.\u00a0Trevisan, S.P. Vadhan, Notions of reducibility between cryptographic primitives, in Proceedings of the 1st Theory of Cryptography Conference, pp. 1\u201320 (2004)","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"9369_CR33","unstructured":"S.\u00a0Rudich, Limits on the Provable Consequences of One-Way Functions. PhD thesis (EECS Department, University of California, Berkeley, 1988)"},{"key":"9369_CR34","doi-asserted-by":"crossref","unstructured":"D.R. Simon, Finding collisions on a one-way street: can secure hash functions be based on general assumptions? in Advances in Cryptology\u2014EUROCRYPT\u201998, pp. 334\u2013345 (1998)","DOI":"10.1007\/BFb0054137"},{"key":"9369_CR35","unstructured":"R.\u00a0Savani, B.\u00a0von Stengel, 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)"},{"key":"9369_CR36","doi-asserted-by":"crossref","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, pp. 475\u2013484 (2014)","DOI":"10.1145\/2591796.2591825"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-020-09369-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-020-09369-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-020-09369-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T21:31:02Z","timestamp":1612819862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-020-09369-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["9369"],"URL":"https:\/\/doi.org\/10.1007\/s00145-020-09369-6","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"30 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"8"}}