{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T17:41:53Z","timestamp":1771609313563,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188870","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"671-684","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["Multi-collision resistance: a paradigm for keyless hash functions"],"prefix":"10.1145","author":[{"given":"Nir","family":"Bitansky","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}]},{"given":"Yael Tauman","family":"Kalai","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}]},{"given":"Omer","family":"Paneth","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0121-8"},{"key":"e_1_3_2_2_2_1","unstructured":"Benny Applebaum and Yoni Moses. 2013.  Benny Applebaum and Yoni Moses. 2013."},{"key":"e_1_3_2_2_3_1","volume-title":"32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings. 486\u2013502","author":"Linear Shrinkage Locally Computable UOWHF"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875552"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/070709244"},{"key":"e_1_3_2_2_6_1","volume-title":"Lower Bounds for Non-Black-Box Zero Knowledge. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings. 384\u2013 393","author":"Barak Boaz"},{"key":"e_1_3_2_2_7_1","volume-title":"International Conference on the Theory and Application of Cryptographic Techniques","author":"Bellare Mihir","year":"1997"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28628-8_17"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_3"},{"key":"e_1_3_2_2_12_1","first-page":"580","article-title":"The Hunting of the SNARK","volume":"2014","author":"Bitansky Nir","year":"2014","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488623"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591859"},{"key":"e_1_3_2_2_15_1","volume-title":"Advances STOC\u201918, June 25\u201329","author":"Black John","year":"2018"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185212"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_35"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008734"},{"key":"e_1_3_2_2_19_1","unstructured":"1008734  1008734"},{"key":"e_1_3_2_2_20_1","volume-title":"USA","author":"Chung Kai-Min","year":"2011"},{"key":"e_1_3_2_2_21_1","unstructured":"Joan Daemen and Vincent Rijmen. 2002.  Joan Daemen and Vincent Rijmen. 2002."},{"key":"e_1_3_2_2_22_1","volume-title":"AES - The Advanced Encryption Standard","author":"Rijndael The Design"},{"key":"e_1_3_2_2_23_1","unstructured":"3- 662- 04722- 4  3- 662- 04722- 4"},{"key":"e_1_3_2_2_24_1","unstructured":"Ivan Damg\u00e5rd. 1989.  Ivan Damg\u00e5rd. 1989."},{"key":"e_1_3_2_2_25_1","volume-title":"9th Annual International Cryptology Conference","author":"Hash Functions A Design Principle","year":"1989"},{"key":"e_1_3_2_2_26_1","volume-title":"13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings. 250\u2013 265","author":"Damg\u00e5rd Ivan","year":"1993"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69407-6_21"},{"key":"e_1_3_2_2_28_1","volume-title":"Steinberger","author":"Dodis Yevgeniy","year":"2011"},{"key":"e_1_3_2_2_29_1","volume-title":"Tallinn","author":"Cs Domain Extension","year":"2011"},{"key":"e_1_3_2_2_30_1","unstructured":"Cynthia Dwork and Moni Naor. 2007.  Cynthia Dwork and Moni Naor. 2007."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703426817"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950623"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Uriel Feige and Adi Shamir. 1989. Zero Knowledge Proofs of Knowledge in Two Rounds. In CRYPTO. 526\u2013544.   Uriel Feige and Adi Shamir. 1989. Zero Knowledge Proofs of Knowledge in Two Rounds. In CRYPTO. 526\u2013544.","DOI":"10.1007\/0-387-34805-0_46"},{"key":"e_1_3_2_2_34_1","first-page":"167","article-title":"On the Existence of Three Round Zero-Knowledge Proofs","volume":"2018","author":"Fleischhacker Nils","year":"2018","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_2_2_35_1","unstructured":"Oded Goldreich and Ariel Kahan. 1996.  Oded Goldreich and Ariel Kahan. 1996."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00208001"},{"key":"e_1_3_2_2_37_1","unstructured":"Oded Goldreich and Hugo Krawczyk. 1996.  Oded Goldreich and Hugo Krawczyk. 1996."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791220688"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_3_2_2_40_1","unstructured":"Oded Goldreich and Yair Oren. 1994.  Oded Goldreich and Yair Oren. 1994."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00195207"},{"key":"e_1_3_2_2_42_1","volume-title":"Expander-Based Constructions of Efficiently Decodable Codes. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001","author":"Guruswami Venkatesan","year":"2001"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_3_2_2_44_1","unstructured":"Satoshi Hada and Toshiaki Tanaka. 1998.  Satoshi Hada and Toshiaki Tanaka. 1998."},{"key":"e_1_3_2_2_45_1","volume-title":"Zero-Knowledge Protocols. In Proceedings of the 18th Annual International Cryptology Conference. 408\u2013423","author":"Round On"},{"key":"e_1_3_2_2_46_1","volume-title":"USA","author":"Haitner Iftach","year":"2015"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536497"},{"key":"e_1_3_2_2_48_1","volume-title":"16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings. 201\u2013215","author":"Halevi Shai","year":"1996"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_3_2_2_50_1","volume-title":"Santa Barbara","author":"Joux Antoine","year":"2004"},{"key":"e_1_3_2_2_51_1","volume-title":"Rothblum","author":"Kalai Yael Tauman","year":"2014"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591809"},{"key":"e_1_3_2_2_53_1","volume-title":"Rothblum","author":"Kalai Yael Tauman","year":"2017"},{"key":"e_1_3_2_2_54_1","volume-title":"USA","author":"From","year":"2017"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-010-9081-y"},{"key":"e_1_3_2_2_56_1","unstructured":"Joe Kilian. 1992.  Joe Kilian. 1992."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365744"},{"key":"e_1_3_2_2_60_1","first-page":"15","article-title":"White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing","volume":"24","author":"Komargodski Ilan","year":"2017","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579323"},{"key":"e_1_3_2_2_62_1","volume-title":"27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings. 187\u2013204","author":"Ueli"},{"key":"e_1_3_2_2_63_1","volume-title":"Papadimitriou","author":"Megiddo Nimrod","year":"1991"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_3_2_2_65_1","volume-title":"9th Annual International Cryptology Conference","author":"Merkle Ralph C.","year":"1989"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_3_2_2_67_1","volume-title":"23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. 96\u2013109","author":"Naor Moni","year":"2003"},{"key":"e_1_3_2_2_68_1","first-page":"164","article-title":"Simultaneous Resettability from Collision Resistance","volume":"19","author":"Ostrovsky Rafail","year":"2012","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"crossref","unstructured":"Rafael Pass. 2003. Simulation in Quasi-Polynomial Time and Its Application to Protocol Composition. In EUROCRYPT. 160\u2013176.   Rafael Pass. 2003. Simulation in Quasi-Polynomial Time and Its Application to Protocol Composition. In EUROCRYPT. 160\u2013176.","DOI":"10.1007\/3-540-39200-9_10"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/11958239_14"},{"key":"e_1_3_2_2_71_1","unstructured":"Dominique Unruh. 2007.  Dominique Unruh. 2007."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188870","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":69,"alternative-id":["10.1145\/3188745.3188870","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188870","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}