{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:49:00Z","timestamp":1770900540464,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Natural Science Foundation of China","award":["62102260"],"award-info":[{"award-number":["62102260"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649752","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1739-1749","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-1075-4297","authenticated-orcid":false,"family":"Akshima","sequence":"first","affiliation":[{"name":"NYU Shanghai, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1504-9943","authenticated-orcid":false,"given":"Tyler","family":"Besselman","sequence":"additional","affiliation":[{"name":"NYU Shanghai, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3664-3928","authenticated-orcid":false,"given":"Siyao","family":"Guo","sequence":"additional","affiliation":[{"name":"NYU Shanghai, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1169-3354","authenticated-orcid":false,"given":"Zhiye","family":"Xie","sequence":"additional","affiliation":[{"name":"NYU Shanghai, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-6304-2765","authenticated-orcid":false,"given":"Yuping","family":"Ye","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China \/ NYU Shanghai, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Akshima David Cash Andrew Drucker and Hoeteck Wee. 2020. Time-Space Tradeofs and Short Collisions in Merkle-Damg\u00e5rd Hash Functions. In CRYPTO. https:\/\/doi.org\/10.1007\/978-3-030-56784-2_6 10.1007\/978-3-030-56784-2_6","DOI":"10.1007\/978-3-030-56784-2_6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","unstructured":"Akshima Xiaoqi Duan Siyao Guo and Qipeng Liu. 2023. On Time-Space Lower Bounds for Finding Short Collisions in Sponge Hash Functions. In TCC. https: \/\/doi.org\/10.1007\/978-3-031-48621-0_9 10.1007\/978-3-031-48621-0_9","DOI":"10.1007\/978-3-031-48621-0_9"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Akshima Siyao Guo and Qipeng Liu. 2022. Time-Space Lower Bounds for Finding Collisions in Merkle-Damg\u00e5rd Hash Functions. In CRYPTO. https: \/\/doi.org\/10.1007\/978-3-031-15982-4_7 10.1007\/978-3-031-15982-4_7","DOI":"10.1007\/978-3-031-15982-4_7"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Benedikt Auerbach Charlotte Hofmann and Guillermo Pascual-Perez. 2023. Generic-Group Lower Bounds via Reductions Between Geometric-Search Problems: With and Without Preprocessing. In TCC. https:\/\/doi.org\/10.1007\/978-3-031-48621-0_11 10.1007\/978-3-031-48621-0_11","DOI":"10.1007\/978-3-031-48621-0_11"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","unstructured":"James Bartusek Fermi Ma and Mark Zhandry. 2019. The Distinction Between Fixed and Random Generators in Group-Based Assumptions. In CRYPTO. https: \/\/doi.org\/10.1007\/978-3-030-26951-7_27 10.1007\/978-3-030-26951-7_27","DOI":"10.1007\/978-3-030-26951-7_27"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-42045-0_17"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Dror Chawin Iftach Haitner and Noam Mazor. 2020. Lower Bounds on the Time\/Memory Tradeof of Function Inversion. In TCC. https:\/\/doi.org\/10.1007\/ 978-3-030-64381-2_11 10.1007\/978-3-030-64381-2_11","DOI":"10.1007\/978-3-030-64381-2_11"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00068"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Sandro Coretti Yevgeniy Dodis and Siyao Guo. 2018. Non-Uniform Bounds in the Random-Permutation Ideal-Cipher and Generic-Group Models. In CRYPTO. https:\/\/doi.org\/10.1007\/978-3-319-96884-1_23 10.1007\/978-3-319-96884-1_23","DOI":"10.1007\/978-3-319-96884-1_23"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Henry Corrigan-Gibbs and Dmitry Kogan. 2018. The Discrete-Logarithm Problem with Preprocessing. In EUROCRYPT. https:\/\/doi.org\/10.1007\/978-3-319-78375-8_14 10.1007\/978-3-319-78375-8_14","DOI":"10.1007\/978-3-319-78375-8_14"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Henry Corrigan-Gibbs and Dmitry Kogan. 2019. The Function-Inversion Problem: Barriers and Opportunities. In TCC. https:\/\/doi.org\/10.1007\/978-3-030-36030-6_16 10.1007\/978-3-030-36030-6_16","DOI":"10.1007\/978-3-030-36030-6_16"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Anindya De Luca Trevisan and Madhur Tulsiani. 2010. Time Space Tradeofs for Attacks against One-Way Functions and PRGs. In CRYPTO. https:\/\/doi.org\/ 10.1007\/978-3-642-14623-7_35 10.1007\/978-3-642-14623-7_35","DOI":"10.1007\/978-3-642-14623-7_35"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Yevgeniy Dodis Siyao Guo and Jonathan Katz. 2017. Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input Revisited. In EUROCRYPT. https: \/\/doi.org\/10.1007\/978-3-319-56614-6_16 10.1007\/978-3-319-56614-6_16","DOI":"10.1007\/978-3-319-56614-6_16"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45611-8_22"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Cody Freitag Ashrujit Ghoshal and Ilan Komargodski. 2022. Time-Space Tradeofs for Sponge Hashing: Attacks and Limitations for Short Collisions. In CRYPTO. https:\/\/doi.org\/10.1007\/978-3-031-15982-4_5 10.1007\/978-3-031-15982-4_5","DOI":"10.1007\/978-3-031-15982-4_5"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Cody Freitag Ashrujit Ghoshal and Ilan Komargodski. 2023. Optimal Security for Keyed Hash Functions: Avoiding Time-Space Tradeofs for Finding Collisions. In EUROCRYPT. https:\/\/doi.org\/10.1007\/978-3-031-30634-1_15 10.1007\/978-3-031-30634-1_15","DOI":"10.1007\/978-3-031-30634-1_15"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Ashrujit Ghoshal and Ilan Komargodski. 2022. On Time-Space Tradeofs for Bounded-Length Collisions in Merkle-Damg\u00e5rd Hashing. In CRYPTO. https: \/\/doi.org\/10.1007\/978-3-031-15982-4_6 10.1007\/978-3-031-15982-4_6","DOI":"10.1007\/978-3-031-15982-4_6"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","unstructured":"Alexander Golovnev Siyao Guo Spencer Peters and Noah Stephens-Davidowitz. 2023. Revisiting Time-Space Tradeofs for Function Inversion. In CRYPTO. https: \/\/doi.org\/10.1007\/978-3-031-38545-2_15 10.1007\/978-3-031-38545-2_15","DOI":"10.1007\/978-3-031-38545-2_15"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.143"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Fabian Kuhn and Ren\u00e9 Struik. 2001. Random Walks Revisited: Extensions of Pollard's Rho Algorithm for Computing Multiple Discrete Logarithms. In SAC. https:\/\/doi.org\/10.1007\/3-540-45537-X_17 10.1007\/3-540-45537-X_17","DOI":"10.1007\/3-540-45537-X_17"},{"key":"e_1_3_2_1_24_1","volume-title":"Jung Hee Cheon, and Jin Hong","author":"Lee Hyung Tae","year":"2011","unstructured":"Hyung Tae Lee, Jung Hee Cheon, and Jin Hong. 2011. Accelerating ID-based encryption based on trapdoor DL using pre-computation. Cryptology ePrint Archive ( 2011 )."},{"key":"e_1_3_2_1_25_1","unstructured":"Joseph P Mihalcik. 2010. An analysis of algorithms for solving discrete logarithms in fixed groups. Ph. D. Dissertation. Citeseer."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Victor Shoup. 1997. Lower Bounds for Discrete Logarithms and Related Problems. In EUROCRYPT. https:\/\/doi.org\/10.1007\/3-540-69053-0_18 10.1007\/3-540-69053-0_18","DOI":"10.1007\/3-540-69053-0_18"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Dominique Unruh. 2007. Random Oracles and Auxiliary Input. In CRYPTO. https:\/\/doi.org\/10.1007\/978-3-540-74143-5_12 10.1007\/978-3-540-74143-5_12","DOI":"10.1007\/978-3-540-74143-5_12"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Aaram Yun. 2015. Generic Hardness of the Multiple Discrete Logarithm Problem. In EUROCRYPT. https:\/\/doi.org\/10.1007\/978-3-662-46803-6_27 10.1007\/978-3-662-46803-6_27","DOI":"10.1007\/978-3-662-46803-6_27"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"R. Zippel. 1979. Probabilistic algorithms for sparse polynomials. In EUROSAM. https:\/\/doi.org\/10.1007\/3-540-09519-5_73 10.1007\/3-540-09519-5_73","DOI":"10.1007\/3-540-09519-5_73"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649752","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649752","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649752"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":30,"alternative-id":["10.1145\/3618260.3649752","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649752","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}