{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:18:44Z","timestamp":1781259524628,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":73,"publisher":"ACM","funder":[{"name":"European Research Council","award":["101041208"],"award-info":[{"award-number":["101041208"]}]},{"name":"Natural Sciences and Engineering Research Council of Canada","award":["RGPIN-2024-04490"],"award-info":[{"award-number":["RGPIN-2024-04490"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718177","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"977-985","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6084-4729","authenticated-orcid":false,"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5481-7276","authenticated-orcid":false,"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9693-9244","authenticated-orcid":false,"given":"Roei","family":"Tell","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585244"},{"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.1109\/CCC.2006.17"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_3_2_1_5_1","volume-title":"Proc. 17th Theory of Cryptography Conference (TCC). 522\u2013551","author":"Bartusek James","unstructured":"James Bartusek, Liron Bronfman, Justin Holmgren, Fermi Ma, and Ron D. Rothblum. 2019. On the (In)security of Kilian-Based SNARGs. In Proc. 17th Theory of Cryptography Conference (TCC). 522\u2013551."},{"key":"e_1_3_2_1_6_1","volume-title":"Proc. 24th Computer Society International Conference COMPCON. 133\u2013137","author":"Blum Manuel","year":"1982","unstructured":"Manuel Blum. 1982. Coin Flipping by Telephone - A Protocol for Solving Impossible Problems. In Proc. 24th Computer Society International Conference COMPCON. 133\u2013137."},{"key":"e_1_3_2_1_7_1","volume-title":"Proc. 1st Conference on Innovations in Theoretical Computer Science (ITCS).","author":"Bogdanov Andrej","year":"2010","unstructured":"Andrej Bogdanov, Kunal Talwar, and Andrew Wan. 2010. Hard Instances for Satisfiability and Quasi-one-way Functions. In Proc. 1st Conference on Innovations in Theoretical Computer Science (ITCS)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56877-1_26"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Gilles Brassard David Chaum and Claude Cr\u00e9peau. 1988. Minimum disclosure proofs of knowledge. 37 156\u2013189.","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316380"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49096-9_17"},{"key":"e_1_3_2_1_12_1","volume-title":"Rothblum","author":"Canetti Ran","year":"2018","unstructured":"Ran Canetti, Yilei Chen, Leonid Reyzin, and Ron D. Rothblum. 2018. Fiat-Shamir and correlation intractability from strong KDM-secure encryption. In Advances in cryptology\u2014EUROCRYPT. 91\u2013122."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008734"},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 646\u2013657","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen, Ce Jin, Rahul Santhanam, and Ryan Williams. 2021. Constructive Separations and Their Consequences. In Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 646\u2013657."},{"key":"e_1_3_2_1_15_1","volume-title":"Proc. 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Chen Lijie","unstructured":"Lijie Chen, Jiatu Li, and Igor C. Oliveira. 2024. Reverse mathematics of complexity lower bounds. In Proc. 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_16_1","first-page":"116","article-title":"Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)","volume":"31","author":"Chen Lijie","year":"2024","unstructured":"Lijie Chen, Ron D. Rothblum, and Roei Tell. 2024. Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?). Electronic Colloquium on Computational Complexity: ECCC, 31 (2024), 116.","journal-title":"Electronic Colloquium on Computational Complexity: ECCC"},{"key":"e_1_3_2_1_17_1","volume-title":"Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 125\u2013136","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen and Roei Tell. 2021. Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. In Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 125\u2013136."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585215"},{"key":"e_1_3_2_1_19_1","volume-title":"Proc. 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 1008\u20131047","author":"Chen Lijie","unstructured":"Lijie Chen, Roei Tell, and R. Ryan Williams. 2023. Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. In Proc. 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 1008\u20131047."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38551-3_20"},{"key":"e_1_3_2_1_21_1","volume-title":"Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 68\u201379","author":"Choudhuri Arka Rai","year":"2021","unstructured":"Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. 2021. SNARGs for \u00b6 from LWE. In Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 68\u201379."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38233-8_16"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703426817"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792230010"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Amos Fiat and Adi Shamir. 1986. How to prove yourself: practical solutions to identification and signature problems. In Advances in cryptology\u2014CRYPTO. 186\u2013194.","DOI":"10.1007\/3-540-47721-7_12"},{"key":"e_1_3_2_1_26_1","first-page":"47","article-title":"Two Comments on Targeted Canonical Derandomizers","volume":"18","author":"Goldreich Oded","year":"2011","unstructured":"Oded Goldreich. 2011. Two Comments on Targeted Canonical Derandomizers. Electronic Colloquium on Computational Complexity: ECCC, 18 (2011), 47.","journal-title":"Electronic Colloquium on Computational Complexity: ECCC"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00195207"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_2_1_29_1","volume-title":"Symposium on Logical Foundations of Computer Science. 108\u2013118","author":"Gurevich Yuri","year":"1989","unstructured":"Yuri Gurevich and Saharon Shelah. 1989. Nearly linear time. In Logic at Botik, Symposium on Logical Foundations of Computer Science. 108\u2013118."},{"key":"e_1_3_2_1_30_1","volume-title":"Sci.","volume":"397","author":"Gutfreund Dan","year":"2006","unstructured":"Dan Gutfreund. 2006. Worst-case vs. algorithmic average-case complexity in the polynomial-time hierarchy. In Approximation, randomization and combinatorial optimization (Lecture Notes in Comput. Sci., Vol. 4110). 386\u2013397."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0235-8"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1802614.1802617"},{"key":"e_1_3_2_1_33_1","volume-title":"Computational Limitations of Small-depth Circuits","author":"H\u00e5stad Johan","unstructured":"Johan H\u00e5stad. 1987. Computational Limitations of Small-depth Circuits. MIT Press."},{"key":"e_1_3_2_1_34_1","volume-title":"Proc. 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 850\u2013858","author":"Holmgren Justin","year":"2018","unstructured":"Justin Holmgren and Alex Lombardi. 2018. Cryptographic hashing from strong one-way functions. In Proc. 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 850\u2013858."},{"key":"e_1_3_2_1_35_1","volume-title":"Proc. 53rd Annual ACM Symposium on Theory of Computing (STOC). 750\u2013760","author":"Holmgren Justin","unstructured":"Justin Holmgren, Alex Lombardi, and Ron D. Rothblum. 2021. Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). In Proc. 53rd Annual ACM Symposium on Theory of Computing (STOC). 750\u2013760."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-07085-3_18"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77870-5_1"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451055"},{"key":"e_1_3_2_1_40_1","volume-title":"Weak Pigeonhole Principle, and Randomized Computation","author":"Je\u0159\u00e1bek Emil","unstructured":"Emil Je\u0159\u00e1bek. 2005. Weak Pigeonhole Principle, and Randomized Computation. Charles University in Prague. Available at https:\/\/eccc.weizmann.ac.il\/resources\/pdf\/jerabek.pdf"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1191333850"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1763"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316411"},{"key":"e_1_3_2_1_44_1","volume-title":"Rothblum","author":"Kalai Yael Tauman","year":"2017","unstructured":"Yael Tauman Kalai, Guy N. Rothblum, and Ron D. Rothblum. 2017. From obfuscation to the security of Fiat-Shamir for proofs. In Advances in cryptology\u2014CRYPTO. 224\u2013251."},{"key":"e_1_3_2_1_45_1","volume-title":"Proc. 24th Annual ACM Symposium on Theory of Computing (STOC). 723\u2013732","author":"Kilian Joe","year":"1992","unstructured":"Joe Kilian. 1992. A note on efficient zero-knowledge proofs and arguments. In Proc. 24th Annual ACM Symposium on Theory of Computing (STOC). 723\u2013732."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"e_1_3_2_1_47_1","volume-title":"Proof complexity. 170","author":"Kraj\u00ed\u010dek Jan","unstructured":"Jan Kraj\u00ed\u010dek. 2019. Proof complexity. 170, Cambridge University Press."},{"key":"e_1_3_2_1_48_1","volume-title":"Round complexity versus randomness complexity in interactive proofs. Theory of Computing, 18","author":"Leshkowitz Maya","year":"2022","unstructured":"Maya Leshkowitz. 2022. Round complexity versus randomness complexity in interactive proofs. Theory of Computing, 18 (2022), Paper No. 13, 65."},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. 55th Annual ACM Symposium on Theory of Computing (STOC). 1051\u20131057","author":"Li Jiatu","unstructured":"Jiatu Li and Igor C. Oliveira. 2023. Unprovability of strong complexity lower bounds in bounded arithmetic. In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC). 1051\u20131057."},{"key":"e_1_3_2_1_50_1","volume-title":"Proc. 26th Annual ACM Symposium on Theory of Computing (STOC). 734\u2013740","author":"Richard","unstructured":"Richard J. Lipton and Neal E. Young. 1994. Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory. In Proc. 26th Annual ACM Symposium on Theory of Computing (STOC). 734\u2013740."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0197-7"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102735"},{"key":"e_1_3_2_1_55_1","volume-title":"Proc. 23rd Advances in cryptology\u2014CRYPTO","author":"Naor Moni","unstructured":"Moni Naor. 2003. On Cryptographic Assumptions and Challenges. In Proc. 23rd Advances in cryptology\u2014CRYPTO, Dan Boneh (Ed.). Springer."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_57_1","first-page":"139","article-title":"Hardness Magnification for Natural Problems","volume":"25","author":"Oliveira Igor Carboni","year":"2018","unstructured":"Igor Carboni Oliveira and Rahul Santhanam. 2018. Hardness Magnification for Natural Problems. Electronic Colloquium on Computational Complexity: ECCC, 25 (2018), 139.","journal-title":"Electronic Colloquium on Computational Complexity: ECCC"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/050641958"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Chris Peikert and Sina Shiehian. 2019. Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors. In Advances in Cryptology - CRYPTO. 89\u2013114.","DOI":"10.1007\/978-3-030-26948-7_4"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.08.004"},{"key":"e_1_3_2_1_61_1","volume-title":"Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic. Logical Methods in Computer Science, 11, 2","author":"Pich J\u00e1n","year":"2015","unstructured":"J\u00e1n Pich. 2015. Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic. Logical Methods in Computer Science, 11, 2 (2015), 2:8, 38."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451117"},{"key":"e_1_3_2_1_63_1","first-page":"798","article-title":"Lower bounds on the monotone complexity of some Boolean functions","volume":"281","author":"Razborov A. A.","year":"1985","unstructured":"A. A. Razborov. 1985. Lower bounds on the monotone complexity of some Boolean functions. Doklady Akademii Nauk SSSR, 281, 4 (1985), 798\u2013801.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_65_1","volume-title":"Feasible mathematics, II (Ithaca","author":"Razborov Alexander A.","year":"1992","unstructured":"Alexander A. Razborov. 1995. Bounded arithmetic and lower bounds in Boolean complexity. In Feasible mathematics, II (Ithaca, NY, 1992) (Progr. Comput. Sci. Appl. Logic, Vol. 13). 344\u2013386."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250854"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_71_1","volume-title":"Proc. 38th Annual IEEE Conference on Computational Complexity (CCC). Art. No. 17","author":"van Melkebeek Dieter","year":"2023","unstructured":"Dieter van Melkebeek and Nicollas Sdroievski. 2023. Instance-wise hardness versus randomness tradeoffs for Arthur-Merlin protocols. In Proc. 38th Annual IEEE Conference on Computational Complexity (CCC). Art. No. 17, 36."},{"key":"e_1_3_2_1_72_1","volume-title":"Proc. 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Art. No. 29","author":"van Melkebeek Dieter","year":"2023","unstructured":"Dieter van Melkebeek and Nicollas Sdroievski. 2023. Leakage resilience, targeted pseudorandom generators, and mild derandomization of Arthur-Merlin protocols. In Proc. 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Art. No. 29, 22."},{"key":"e_1_3_2_1_73_1","volume-title":"Computer science\u2014theory and applications (Lecture Notes in Comput. Sci.","author":"Vereshchagin Nikolay","unstructured":"Nikolay Vereshchagin. 2013. Improving on Gutfreund, Shaltiel, and Ta-Shma\u2019s paper \u201cIf NP languages are hard on the worst-case, then it is easy to find their hard instances\u201d. In Computer science\u2014theory and applications (Lecture Notes in Comput. Sci., Vol. 7913). 203\u2013211."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3718177","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:42:09Z","timestamp":1750693329000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":73,"alternative-id":["10.1145\/3717823.3718177","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718177","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"}}]}}