{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:11Z","timestamp":1750309511623,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:00:00Z","timestamp":1718064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["573\/16 and 1903\/20"],"award-info":[{"award-number":["573\/16 and 1903\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["757731"],"award-info":[{"award-number":["757731"]}]},{"DOI":"10.13039\/501100012443","name":"BIU Center for Research in Applied Cryptography and Cyber Security","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012443","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israel National Cyber Bureau"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1612\/17 and 2669\/21"],"award-info":[{"award-number":["1612\/17 and 2669\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            An average-case variant of the\n            <jats:italic>k<\/jats:italic>\n            -SUM conjecture asserts that finding\n            <jats:italic>k<\/jats:italic>\n            numbers that sum to 0 in a list of\n            <jats:italic>r<\/jats:italic>\n            random numbers, each of the order\n            <jats:italic>r<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            , cannot be done in much less than\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(r^{\\lceil k\/2 \\rceil }\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            time. However, in the\n            <jats:italic>dense regime<\/jats:italic>\n            of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner\u2019s\n            <jats:italic>k<\/jats:italic>\n            -tree algorithm. Such algorithms for\n            <jats:italic>k<\/jats:italic>\n            -SUM in the dense regime have many applications, notably in cryptanalysis.\n          <\/jats:p>\n          <jats:p>\n            In this article, assuming the average-case\n            <jats:italic>k<\/jats:italic>\n            -SUM conjecture, we prove that known algorithms are essentially optimal for\n            <jats:italic>k<\/jats:italic>\n            = 3,4,5. For\n            <jats:italic>k<\/jats:italic>\n            &gt; 5, we prove the optimality of the\n            <jats:italic>k<\/jats:italic>\n            -tree algorithm for a limited range of parameters. We also prove similar results for\n            <jats:italic>k<\/jats:italic>\n            -XOR, where the sum is replaced with exclusive or.\n          <\/jats:p>\n          <jats:p>\n            Our results are obtained by a self-reduction that, given an instance of\n            <jats:italic>k<\/jats:italic>\n            -SUM that has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense\n            <jats:italic>k<\/jats:italic>\n            -SUM oracle and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle\u2019s solutions, even though its inputs are highly correlated.\n          <\/jats:p>","DOI":"10.1145\/3653014","type":"journal-article","created":{"date-parts":[[2024,3,17]],"date-time":"2024-03-17T07:42:27Z","timestamp":1710661347000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense\n            <i>k<\/i>\n            -SUM and\n            <i>k<\/i>\n            -XOR"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2864-5121","authenticated-orcid":false,"given":"Itai","family":"Dinur","sequence":"first","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1591-9840","authenticated-orcid":false,"given":"Nathan","family":"Keller","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9485-890X","authenticated-orcid":false,"given":"Ohad","family":"Klein","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_4_4_2","volume-title":"Log-concave Probability Distributions: Theory and Statistical Testing","author":"An Mark Yuying","year":"1996","unstructured":"Mark Yuying An. 1996. Log-concave Probability Distributions: Theory and Statistical Testing. Game Theory and Information. University Library of Munich, Germany. Retrieved from https:\/\/EconPapers.repec.org\/RePEc:wpa:wuwpga:9611002"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/060669474"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_26"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_31"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77870-5_2"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1093\/ACPROF:OSO\/9780199535255.001.0001"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.13154\/tosc.v2018.i1.254-276"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.29"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46416-6_3"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_19"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-018-00594-6"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITC.2021.24"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-013-9164-7"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1945-08454-7"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384342"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_12"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73009"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9946-9"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781420070033"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_20"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_8"},{"issue":"12","key":"e_1_3_4_27_2","first-page":"277","article-title":"On the number of real roots of a random algebraic equation (III)","volume":"54","author":"Littlewood John Edensor","year":"1943","unstructured":"John Edensor Littlewood and A. Cyril Offord. 1943. On the number of real roots of a random algebraic equation (III). Rec. Math. (Mat. Sbornik). Nouvelle S\u00e9rie 54, 12 (1943), 277\u2013286.","journal-title":"Rec. Math. (Mat. Sbornik). Nouvelle S\u00e9rie"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28628-8_25"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_32"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_10"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-011-9097-y"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451024"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48800-3_28"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_4_35_2","article-title":"Higher lower bounds from the 3sum conjecture","author":"Pettie Seth","year":"2015","unstructured":"Seth Pettie. 2015. Higher lower bounds from the 3sum conjecture. In Proceedings of the Fine-grained Complexity and Algorithm Design Workshop at the Simons Institute.","journal-title":"Proceedings of the Fine-grained Complexity and Algorithm Design Workshop at the Simons Institute"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1142\/9789813272880_0188"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45708-9_19"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653014","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3653014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:59Z","timestamp":1750295879000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,11]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3653014"],"URL":"https:\/\/doi.org\/10.1145\/3653014","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2024,6,11]]},"assertion":[{"value":"2022-07-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}