{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,28]],"date-time":"2026-05-28T02:13:46Z","timestamp":1779934426784,"version":"3.53.1"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1262\/18 and 2137\/19"],"award-info":[{"award-number":["1262\/18 and 2137\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["NDSEG Fellowship"],"award-info":[{"award-number":["NDSEG Fellowship"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CNS-1350619"],"award-info":[{"award-number":["CNS-1350619"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["W911NF-15-C-0226"],"award-info":[{"award-number":["W911NF-15-C-0226"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-15-C-0236"],"award-info":[{"award-number":["W911NF-15-C-0236"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451116","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"750-760","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Fiat\u2013Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge)"],"prefix":"10.1145","author":[{"given":"Justin","family":"Holmgren","sequence":"first","affiliation":[{"name":"NTT Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Lombardi","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0058034"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45727-3_22"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959885"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54242-8_2"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238212"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36033-7_20"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89577"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48329-2_21"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_11"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188870"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the International Congress of Mathematicians. 1, Pages 2.","author":"Blum Manuel","year":"1986","unstructured":"Manuel Blum. 1986. How to prove a theorem so no one else can claim it. In Proceedings of the International Congress of Mathematicians. 1, Pages 2."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.72"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56877-1_26"},{"key":"e_1_3_2_1_15_1","volume-title":"Rothblum","author":"Canetti Ran","year":"2018","unstructured":"Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, and Ron D. Rothblum. 2018. Fiat-Shamir From Simpler Assumptions. Cryptology ePrint Archive, Report 2018\/1004. https:\/\/eprint.iacr.org\/2018\/1004"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316380"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49096-9_17"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_4"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276741"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20465-4_19"},{"key":"e_1_3_2_1_22_1","volume-title":"ECCC, 2020","author":"Doron Dean","year":"2020","unstructured":"Dean Doron and Mary Wootters. 2020. High-Probability List-Recovery, and Applications to Heavy Hitters. ECCC, 2020. https:\/\/eccc.weizmann.ac.il\/report\/2020\/162\/"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814626"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89549"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47721-7_12"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78372-7_1"},{"key":"e_1_3_2_1_27_1","volume-title":"Concatenated codes","author":"Forney G David","year":"1966","unstructured":"G David Forney. 1966. Concatenated codes. 1966."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993651"},{"key":"e_1_3_2_1_29_1","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"Goldreich Oded","unstructured":"Oded Goldreich. 2011. A sample of samplers: A computational perspective on sampling. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer. Pages 302\u2013332."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791220688"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47721-7_11"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00195207"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238185"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22178"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45727-3_23"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959942"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510023"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780562"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_59"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.13"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743426"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_9"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_57"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00085"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_49_1","volume-title":"Zero-Knowledge Proofs from Information-Theoretic Proof Systems","author":"Ishai Yuval","year":"2020","unstructured":"Yuval Ishai. 2020. Zero-Knowledge Proofs from Information-Theoretic Proof Systems. 2020. https:\/\/zkproof.org\/2020\/08\/12\/information-theoretic-proof-systems\/"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250794"},{"key":"e_1_3_2_1_51_1","first-page":"2020","article-title":"SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE","volume":"2020","author":"Jawale Ruta","year":"2020","unstructured":"Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang. 2020. SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE. IACR Cryptol. ePrint Arch, 2020, 2020. Pages 980.","journal-title":"IACR Cryptol. ePrint Arch"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63715-0_8"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78375-8_6"},{"key":"e_1_3_2_1_55_1","volume-title":"egue, and Radu Titiu","author":"Nguyen Khoa","year":"2019","unstructured":"Beno\\^\\i t Libert, Khoa Nguyen, Alain Passel\\`egue, and Radu Titiu. 2019. Simulation-Sound Arguments for LWE and Applications to KDM-CCA2 Security. Cryptology ePrint Archive, Report 2019\/908. https:\/\/eprint.iacr.org\/2019\/908"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56877-1_22"},{"key":"e_1_3_2_1_60_1","first-page":"10","volume-title":"Proceedings of STOC 1990","author":"Lund C","year":"1990","unstructured":"C Lund, L Fortnow, H Karloff, and N Nisan. 1990. The polynomial-time hierarchy has interactive proofs. Proceedings of STOC 1990, 1990. Pages 2\u201310."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74143-5_11"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48184-2_32"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48071-4_9"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21916"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.29"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26948-7_4"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0034852"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780603"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.42"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365734"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"crossref","unstructured":"Salil P. Vadhan. 2012. Pseudorandomness. Now Publishers Inc.. isbn:1601985940 https:\/\/people.seas.harvard.edu\/ salil\/pseudorandomness\/","DOI":"10.1561\/9781601985958"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451116","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451116","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":67,"alternative-id":["10.1145\/3406325.3451116","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451116","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}