{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:44Z","timestamp":1750694804770,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585244","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1537-1544","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Constant-Round Arguments from One-Way Functions"],"prefix":"10.1145","author":[{"given":"Noga","family":"Amit","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]},{"given":"Guy N.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Apple, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Locally computable UOWHF with linear shrinkage. IACR Cryptol. ePrint Arch., page 423","author":"Applebaum Benny","year":"2013","unstructured":"Benny Applebaum and Yoni Moses . Locally computable UOWHF with linear shrinkage. IACR Cryptol. ePrint Arch., page 423 , 2013 . Benny Applebaum and Yoni Moses. Locally computable UOWHF with linear shrinkage. IACR Cryptol. ePrint Arch., page 423, 2013."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/070709244"},{"key":"e_1_3_2_1_5_1","first-page":"56","volume-title":"8th Annual International Cryptology Conference","author":"Ben-Or Michael","year":"1988","unstructured":"Michael Ben-Or , Oded Goldreich , Shafi Goldwasser , Johan H\u00e5stad , Joe Kilian , Silvio Micali , and Phillip Rogaway . Everything provable is provable in zero-knowledge. In Advances in Cryptology - CRYPTO \u201988 , 8th Annual International Cryptology Conference , Santa Barbara, California, USA , August 21-25, 1988 , Proceedings, pages 37\u2013 56 , 1988. Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan H\u00e5stad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In Advances in Cryptology - CRYPTO \u201988, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings, pages 37\u201356, 1988."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188870"},{"key":"e_1_3_2_1_7_1","volume-title":"17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings","volume":"1294","author":"Bellare Mihir","year":"1997","unstructured":"Mihir Bellare and Phillip Rogaway . Collision-resistant hashing : Towards making uowhfs practical. In Burton S. Kaliski Jr., editor, Advances in Cryptology - CRYPTO \u201997 , 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings , volume 1294 of Lecture Notes in Computer Science, pages 470\u2013484. Springer , 1997 . Mihir Bellare and Phillip Rogaway. Collision-resistant hashing: Towards making uowhfs practical. In Burton S. Kaliski Jr., editor, Advances in Cryptology - CRYPTO \u201997, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, volume 1294 of Lecture Notes in Computer Science, pages 470\u2013484. Springer, 1997."},{"key":"e_1_3_2_1_8_1","first-page":"79","volume-title":"LWE. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021","author":"Choudhuri Arka Rai","year":"2022","unstructured":"Arka Rai Choudhuri , Abhishek Jain , and Zhengzhong Jin . Snargs for P from LWE. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 , Denver, CO, USA , February 7-10, 2022 , pages 68\u2013 79 . IEEE, 2021. Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. Snargs for P from LWE. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 68\u201379. IEEE, 2021."},{"issue":"1","key":"e_1_3_2_1_9_1","first-page":"114","volume":"28","author":"Chandra Ashok K.","year":"1981","unstructured":"Ashok K. Chandra , Dexter Kozen , and Larry J . Stockmeyer. Alternation. J. ACM , 28 ( 1 ): 114 \u2013 133 , 1981 . Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114\u2013133, 1981.","journal-title":"Stockmeyer. Alternation. J. ACM"},{"key":"e_1_3_2_1_10_1","series-title":"Lecture Notes in Computer Science","first-page":"427","volume-title":"Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference","author":"Damg\u00e5rd Ivan","year":"1989","unstructured":"Ivan Damg\u00e5rd . A design principle for hash functions . In Gilles Brassard, editor, Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference , Santa Barbara, California, USA , August 20-24, 1989 , Proceedings , volume 435 of Lecture Notes in Computer Science , pages 416\u2013 427 . Springer, 1989. Ivan Damg\u00e5rd. A design principle for hash functions. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 416\u2013427. Springer, 1989."},{"key":"e_1_3_2_1_11_1","volume-title":"8th Annual Symposium on Theoretical Aspects of Computer Science","volume":"480","author":"Fortnow Lance","year":"1991","unstructured":"Lance Fortnow and Carsten Lund . Interactive proof systems and alternating time-space complexity. In Christian Choffrut and Matthias Jantzen, editors, STACS 91 , 8th Annual Symposium on Theoretical Aspects of Computer Science , Hamburg, Germany , February 14-16, 1991 , Proceedings, volume 480 of Lecture Notes in Computer Science, pages 263\u2013274. Springer, 1991. Lance Fortnow and Carsten Lund. Interactive proof systems and alternating time-space complexity. In Christian Choffrut and Matthias Jantzen, editors, STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, February 14-16, 1991, Proceedings, volume 480 of Lecture Notes in Computer Science, pages 263\u2013274. Springer, 1991."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00116-1"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_3_2_1_17_1","volume-title":"TR17-101","author":"Goldreich Oded","year":"2017","unstructured":"Oded Goldreich . On the doubly-efficient interactive proof systems of GKR. Electron. Colloquium Comput. Complex ., TR17-101 , 2017 . Oded Goldreich. On the doubly-efficient interactive proof systems of GKR. Electron. Colloquium Comput. Complex., TR17-101, 2017."},{"key":"e_1_3_2_1_18_1","volume-title":"8th Innovations in Theoretical Computer Science Conference, ITCS 2017","author":"Gur Tom","year":"2017","unstructured":"Tom Gur and Ron D. Rothblum . A hierarchy theorem for interactive proofs of proximity . In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017 , January 9-11, 2017 , Berkeley, CA, USA, pages 39:1\u201339:43 , 2017. Tom Gur and Ron D. Rothblum. A hierarchy theorem for interactive proofs of proximity. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 39:1\u201339:43, 2017."},{"key":"e_1_3_2_1_19_1","series-title":"Lecture Notes in Computer Science","first-page":"351","volume-title":"Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation","author":"Goldreich Oded","unstructured":"Oded Goldreich and Guy N. Rothblum . Constant-round interactive proof systems for AC0[2] and NC1 . In Oded Goldreich, editor, Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation , volume 12050 of Lecture Notes in Computer Science , pages 326\u2013 351 . Springer, 2020. Oded Goldreich and Guy N. Rothblum. Constant-round interactive proof systems for AC0[2] and NC1. In Oded Goldreich, editor, Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation, volume 12050 of Lecture Notes in Computer Science, pages 326\u2013351. Springer, 2020."},{"key":"e_1_3_2_1_20_1","first-page":"73","article-title":"Private coins versus public coins in interactive proof systems","volume":"5","author":"Goldwasser Shafi","year":"1989","unstructured":"Shafi Goldwasser and Michael Sipser . Private coins versus public coins in interactive proof systems . Adv. Comput. Res. , 5 : 73 \u2013 90 , 1989 . Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Adv. Comput. Res., 5:73\u201390, 1989.","journal-title":"Adv. Comput. Res."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-002-0169-0"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938438"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00085"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/080725404"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_3_2_1_26_1","volume-title":"Zero-knowledge proofs from information-theoretic proof systems - part i.","author":"Ishai Yuval","year":"2020","unstructured":"Yuval Ishai . Zero-knowledge proofs from information-theoretic proof systems - part i. Available at https:\/\/zkproof.org\/2020\/08\/12\/information-theoretic-proof-systems\/, 2020 . Yuval Ishai. Zero-knowledge proofs from information-theoretic proof systems - part i. Available at https:\/\/zkproof.org\/2020\/08\/12\/information-theoretic-proof-systems\/, 2020."},{"key":"e_1_3_2_1_27_1","volume-title":"Zero-knowledge proofs from information-theoretic proof systems - part ii.","author":"Ishai Yuval","year":"2020","unstructured":"Yuval Ishai . Zero-knowledge proofs from information-theoretic proof systems - part ii. Available at https:\/\/zkproof.org\/2020\/10\/15\/information-theoretic-proof-systems-part-ii\/, 2020 . Yuval Ishai. Zero-knowledge proofs from information-theoretic proof systems - part ii. Available at https:\/\/zkproof.org\/2020\/10\/15\/information-theoretic-proof-systems-part-ii\/, 2020."},{"key":"e_1_3_2_1_28_1","series-title":"Lecture Notes in Computer Science","first-page":"51","volume-title":"Advances in Cryptology - CRYPTO \u201987, A Conference on the Theory and Applications of Cryptographic Techniques","author":"Impagliazzo Russell","year":"1987","unstructured":"Russell Impagliazzo and Moti Yung . Direct minimum-knowledge computations . In Carl Pomerance, editor, Advances in Cryptology - CRYPTO \u201987, A Conference on the Theory and Applications of Cryptographic Techniques , Santa Barbara, California, USA , August 16-20, 1987 , Proceedings , volume 293 of Lecture Notes in Computer Science , pages 40\u2013 51 . Springer, 1987. Russell Impagliazzo and Moti Yung. Direct minimum-knowledge computations. In Carl Pomerance, editor, Advances in Cryptology - CRYPTO \u201987, A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings, volume 293 of Lecture Notes in Computer Science, pages 40\u201351. Springer, 1987."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_1_30_1","volume-title":"On constructing universal one-way hash functions from arbitrary one-way functions","author":"Katz Jonathan","year":"2005","unstructured":"Jonathan Katz and Chiu-Yuen Koo . On constructing universal one-way hash functions from arbitrary one-way functions , 2005 . jkatz@cs.umd.edu 13051 received 16 Sep 2005, last revised 24 Sep 2005. Jonathan Katz and Chiu-Yuen Koo. On constructing universal one-way hash functions from arbitrary one-way functions, 2005. jkatz@cs.umd.edu 13051 received 16 Sep 2005, last revised 24 Sep 2005."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78375-8_6"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456867"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_34_1","series-title":"Lecture Notes in Computer Science","first-page":"446","volume-title":"Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference","author":"Merkle Ralph C.","year":"1989","unstructured":"Ralph C. Merkle . One way hash functions and DES . In Gilles Brassard, editor, Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference , Santa Barbara, California, USA , August 20-24, 1989 , Proceedings , volume 435 of Lecture Notes in Computer Science , pages 428\u2013 446 . Springer, 1989. Ralph C. Merkle. One way hash functions and DES. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO \u201989, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 428\u2013446. Springer, 1989."},{"key":"e_1_3_2_1_35_1","first-page":"453","volume-title":"FOCS","author":"Micali Silvio","year":"1994","unstructured":"Silvio Micali . CS proofs (extended abstracts) . In FOCS , pages 436\u2013 453 , 1994 . Silvio Micali. CS proofs (extended abstracts). In FOCS, pages 436\u2013453, 1994."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 21st Annual ACM Symposium on Theory of Computing","author":"Naor Moni","year":"1989","unstructured":"Moni Naor and Moti Yung . Universal one-way hash functions and their cryptographic applications. In David S. Johnson, editor , Proceedings of the 21st Annual ACM Symposium on Theory of Computing , May 14-17, 1989 , Seattle, Washington, USA, pages 33\u201343. ACM , 1989. Moni Naor and Moti Yung. Universal one-way hash functions and their cryptographic applications. In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 33\u201343. ACM, 1989."},{"key":"e_1_3_2_1_38_1","volume-title":"Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333\u2013338","author":"Razborov Alexander A.","year":"1987","unstructured":"Alexander A. Razborov . Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333\u2013338 , 1987 . Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333\u2013338, 1987."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100269"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897652"},{"key":"e_1_3_2_1_41_1","volume-title":"33rd Computational Complexity Conference, CCC 2018","author":"Reingold Omer","year":"2018","unstructured":"Omer Reingold , Guy N. Rothblum , and Ron D. Rothblum . Efficient batch verification for UP . In 33rd Computational Complexity Conference, CCC 2018 , June 22-24, 2018 , San Diego, CA, USA, pages 22:1\u201322:23 , 2018. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Efficient batch verification for UP. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 22:1\u201322:23, 2018."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-17510-7"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488709"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Daniel R.\n      Simon\n    .\n  Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In Kaisa Nyberg editor Advances in Cryptology - EUROCRYPT \u201998 International Conference on the Theory and Application of Cryptographic Techniques Espoo Finland May 31 - June 4 1998 Proceeding volume \n  1403\n   of \n  Lecture Notes in Computer Science pages 334\u2013\n  345\n  . Springer 1998. \t\t\t\t  Daniel R. Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In Kaisa Nyberg editor Advances in Cryptology - EUROCRYPT \u201998 International Conference on the Theory and Application of Cryptographic Techniques Espoo Finland May 31 - June 4 1998 Proceeding volume 1403 of Lecture Notes in Computer Science pages 334\u2013345. Springer 1998.","DOI":"10.1007\/BFb0054137"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987","author":"Smolensky Roman","year":"1987","unstructured":"Roman Smolensky . Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor , Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987 , New York, New York, USA, pages 77\u201382. ACM , 1987 . Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77\u201382. ACM, 1987."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60615-7"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781638281252"},{"key":"e_1_3_2_1_49_1","unstructured":"Hoeteck\n      Wee\n    .\n  On round-efficient argument systems\n  . In Lu\u00eds Caires Giuseppe F. Italiano Lu\u00eds Monteiro Catuscia Palamidessi and Moti Yung editors Automata Languages\n   and Programming 32nd International Colloquium ICALP \n  2005 Lisbon Portugal July 11-15 2005 Proceedings volume \n  3580\n   of \n  Lecture Notes in Computer Science pages 140\u2013\n  152\n  . Springer 2005. \t\t\t\t  Hoeteck Wee. On round-efficient argument systems. In Lu\u00eds Caires Giuseppe F. Italiano Lu\u00eds Monteiro Catuscia Palamidessi and Moti Yung editors Automata Languages and Programming 32nd International Colloquium ICALP 2005 Lisbon Portugal July 11-15 2005 Proceedings volume 3580 of Lecture Notes in Computer Science pages 140\u2013152. Springer 2005."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:02Z","timestamp":1750178822000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":49,"alternative-id":["10.1145\/3564246.3585244","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585244","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}