{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005005,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CNS-2349972,CNS-2055510"],"award-info":[{"award-number":["CNS-2349972,CNS-2055510"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718159","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"944-954","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-7755-4652","authenticated-orcid":false,"given":"Liyan","family":"Chen","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6307-204X","authenticated-orcid":false,"given":"Cody","family":"Freitag","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2233-3768","authenticated-orcid":false,"given":"Zhengzhong","family":"Jin","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4981-1643","authenticated-orcid":false,"given":"Daniel","family":"Wichs","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"},{"name":"NTT Research, Sunnyvale, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22318-1_6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36033-7_20"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.36"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22365-5_21"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.94"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Nir Bitansky Omer Paneth Dana Shamir and Tomer Solomon. 2023. Non-interactive Universal Arguments. 132\u2013158. https:\/\/doi.org\/10.1007\/978-3-031-38545-2_5 10.1007\/978-3-031-38545-2_5","DOI":"10.1007\/978-3-031-38545-2_5"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_30"},{"key":"e_1_3_2_1_9_1","unstructured":"2013. 45th ACM STOC Dan Boneh Tim Roughgarden and Joan Feigenbaum (Eds.). ACM Press."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_9"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38551-3_20"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316400"},{"key":"e_1_3_2_1_15_1","volume-title":"Rothblum","author":"Choudhuri Arka Rai","year":"2019","unstructured":"Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. 2019. PPAD-Hardness via Iterated Squaring Modulo a Composite. Cryptology ePrint Archive, Paper 2019\/667. https:\/\/eprint.iacr.org\/2019\/667"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84259-8_14"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00016"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47989-6_14"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","unstructured":"Lalita Devadas Rishab Goyal Yael Kalai and Vinod Vaikuntanathan. 2022. Rate-1 Non-Interactive Arguments for Batch-NP and Applications. 1057\u20131068. https:\/\/doi.org\/10.1109\/FOCS54457.2022.00103 10.1109\/FOCS54457.2022.00103","DOI":"10.1109\/FOCS54457.2022.00103"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45727-3_5"},{"key":"e_1_3_2_1_22_1","unstructured":"2022. 63rd FOCS. IEEE Computer Society Press."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5_20"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374407"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488678"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48071-4_16"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Sergey Gorbunov Vinod Vaikuntanathan and Hoeteck Wee. 2013. Attribute-based encryption for circuits. 545\u2013554. https:\/\/doi.org\/10.1145\/2488608.2488677 10.1145\/2488608.2488677","DOI":"10.1145\/2488608.2488677"},{"volume-title":"CRYPTO","year":"2023","key":"e_1_3_2_1_30_1","unstructured":"2023. CRYPTO 2023, Part II, Helena Handschuh and Anna Lysyanskaya (Eds.) (LNCS, Vol. 14082). Springer, Cham."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451116"},{"key":"e_1_3_2_1_32_1","first-page":"1128","article-title":"Hardness of Continuous Local Search","volume":"49","author":"Hub\u00e1cek Pavel","year":"2020","unstructured":"Pavel Hub\u00e1cek and Eylon Yogev. 2020. Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. SIAM J. Comput., 49, 6 (2020), 1128\u20131172.","journal-title":"Query Complexity and Cryptographic Lower Bounds. SIAM J. Comput."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-07085-3_18"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451055"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Zhengzhong Jin Yael Kalai Alex Lombardi and Vinod Vaikuntanathan. 2024. SNARGs under LWE via Propositional Proofs. 1750\u20131757. https:\/\/doi.org\/10.1145\/3618260.3649770 10.1145\/3618260.3649770","DOI":"10.1145\/3618260.3649770"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585200"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30617-4_16"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Yael Tauman Kalai Omer Paneth and Lisa Yang. 2020. Delegation with Updatable Unambiguous Proofs and PPAD-Hardness. 652\u2013673. https:\/\/doi.org\/10.1007\/978-3-030-56877-1_23 10.1007\/978-3-030-56877-1_23","DOI":"10.1007\/978-3-030-56877-1_23"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90459-3_12"},{"volume-title":"Samir Khuller and Virginia Vassilevska Williams (Eds.)","author":"ACM","key":"e_1_3_2_1_40_1","unstructured":"2021. 53rd ACM STOC, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM Press."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15802-5_16"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_14"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","unstructured":"Alex Lombardi and Vinod Vaikuntanathan. 2020. Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs. 632\u2013651. https:\/\/doi.org\/10.1007\/978-3-030-56877-1_22 10.1007\/978-3-030-56877-1_22","DOI":"10.1007\/978-3-030-56877-1_22"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45708-9_38"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365746"},{"volume-title":"CRYPTO","year":"2020","key":"e_1_3_2_1_46_1","unstructured":"2020. CRYPTO 2020, Part III, Daniele Micciancio and Thomas Ristenpart (Eds.) (LNCS, Vol. 12172). Springer, Cham."},{"key":"e_1_3_2_1_47_1","unstructured":"2024. 56th ACM STOC Bojan Mohar Igor Shinkar and Ryan O\u2019Donnell (Eds.). ACM Press."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.23"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","unstructured":"Omer Paneth and Rafael Pass. 2022. Incrementally Verifiable Computation via Rate-1 Batch Arguments. 1045\u20131056. https:\/\/doi.org\/10.1109\/FOCS54457.2022.00102 10.1109\/FOCS54457.2022.00102","DOI":"10.1109\/FOCS54457.2022.00102"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897652"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591825"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90097-1"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78524-8_1"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15979-4_15"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649671"},{"key":"e_1_3_2_1_59_1","volume-title":"Wu","author":"Waters Brent","year":"2024","unstructured":"Brent Waters and David J. Wu. 2024. A Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP. Cryptology ePrint Archive, Paper 2024\/933. https:\/\/eprint.iacr.org\/2024\/933"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68403-6_3"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718159","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:41:06Z","timestamp":1750693266000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":60,"alternative-id":["10.1145\/3717823.3718159","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718159","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}