{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:59Z","timestamp":1781031419900,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100002744","name":"Bar-Ilan University","doi-asserted-by":"publisher","award":["Institutional Open Access Agreement"],"award-info":[{"award-number":["Institutional Open Access Agreement"]}],"id":[{"id":"10.13039\/501100002744","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800873","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1660-1671","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2864-5121","authenticated-orcid":false,"given":"Itai","family":"Dinur","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Faculty of Computer and Information Science, Beer-Sheva, Israel"},{"name":"Georgetown University, Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1591-9840","authenticated-orcid":false,"given":"Nathan","family":"Keller","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Department of Mathematics, Ramat-Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2175-8728","authenticated-orcid":false,"given":"Avichai","family":"Marmor","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Department of Mathematics, Ramat-Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Akshima Tyler Besselman Kai-Min Chung Siyao Guo and Tzu-Yi Yang. 2025. Tight Quantum Time-Space Tradeoffs for Permutation Inversion. arxiv:2510.12112."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649752"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56784-2_6"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-024-09491-9"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnq114"},{"key":"e_1_3_2_1_7_1","volume-title":"The Distinction Between Fixed and Random Generators in Group-Based Assumptions. In CRYPTO 2019 (Lecture Notes in Computer Science","volume":"830","author":"Bartusek James","year":"2019","unstructured":"James Bartusek, Fermi Ma, and Mark Zhandry. 2019. The Distinction Between Fixed and Random Generators in Group-Based Assumptions. In CRYPTO 2019 (Lecture Notes in Computer Science, Vol. 11693). Springer, 801\u2013830."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-42045-0_17"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45539-6_41"},{"key":"e_1_3_2_1_10_1","unstructured":"Pietro Caputo and Justin Salez. 2024. Entropy factorization via curvature. arxiv:2407.13457."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64381-2_11"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-018-9295-y"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch19"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90019-1"},{"key":"e_1_3_2_1_15_1","volume-title":"Tight Quantum Time-Space Tradeoffs for Function Inversion. In FOCS","author":"Chung Kai-Min","year":"2020","unstructured":"Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian. 2020. Tight Quantum Time-Space Tradeoffs for Function Inversion. In FOCS 2020. IEEE, 673\u2013684."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47989-6_9"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_23"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78375-8_14"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36030-6_16"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57332-1_46"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63697-9_18"},{"key":"e_1_3_2_1_23_1","unstructured":"Itai Dinur Nathan Keller and Avichai Marmor. 2025. Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations. arxiv:2505.00894."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56614-6_16"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-013-9164-7"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.39"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900025"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280512"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45611-8_22"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15982-4_5"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITC.2024.5"},{"key":"e_1_3_2_1_32_1","unstructured":"David Galvin. 2014. Three tutorial lectures on entropy and counting. arxiv:1406.7872."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/RSA.20532"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892119"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384342"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_15"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90459-3_7"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00019"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1980.1056220"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649751"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15369-3_46"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-003-0052-4"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/8508"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1283920.1283929"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718280"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302749"},{"key":"e_1_3_2_1_47_1","volume-title":"Master\u2019s thesis. Naval Postgraduate School","author":"Mihalcik Joseph P.","unstructured":"Joseph P. Mihalcik. 2010. An analysis of algorithms for solving discrete logarithms in fixed groups, Master\u2019s thesis. Naval Postgraduate School, Monterey, California."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1978-0491431-9"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2018.V014A020"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/020\/0316385"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-69053-0_18"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74143-5_12"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060669"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800873","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:58:51Z","timestamp":1781027931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800873"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":55,"alternative-id":["10.1145\/3798129.3800873","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800873","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}