{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:49:42Z","timestamp":1782971382869,"version":"3.54.5"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T00:00:00Z","timestamp":1781568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"ERC","award":["638121"],"award-info":[{"award-number":["638121"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["666\/19 and 836\/23"],"award-info":[{"award-number":["666\/19 and 836\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>\n                    In a distributed coin-flipping protocol,\n                    <jats:xref ref-type=\"bibr\">Blum<\/jats:xref>\n                    [ACM Transactions on Computer Systems \u201983], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip,\n                    <jats:xref ref-type=\"bibr\">Ben-Or and Linial<\/jats:xref>\n                    [FOCS \u201985], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt\n                    <jats:italic toggle=\"yes\">along<\/jats:italic>\n                    the protocol execution.\n                    <jats:xref ref-type=\"bibr\">Ben-Or and Linial<\/jats:xref>\n                    proved that the\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    -party majority protocol is resilient to\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\sqrt {n})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    corruptions, and conjectured this is a tight upper bound for any\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for\n                    <jats:italic toggle=\"yes\">single-turn<\/jats:italic>\n                    (each party sends a single message)\n                    <jats:italic toggle=\"yes\">single-bit<\/jats:italic>\n                    (a message is one bit) protocols\n                    <jats:xref ref-type=\"bibr\">Lichtenstein et al.<\/jats:xref>\n                    [Combinatorica \u201989],\n                    <jats:italic toggle=\"yes\">symmetric<\/jats:italic>\n                    protocols\n                    <jats:xref ref-type=\"bibr\">Goldwasser et al.<\/jats:xref>\n                    [ICALP \u201915], and recently for (arbitrary message length) single-turn protocols\n                    <jats:xref ref-type=\"bibr\">Tauman Kalai et al.<\/jats:xref>\n                    [DISC \u201918]. Yet, the question of many-turn protocols was left entirely open.\n                  <\/jats:p>\n                  <jats:p>\n                    In this work, we close the above gap, proving that\n                    <jats:italic toggle=\"yes\">no<\/jats:italic>\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    -party protocol (of any round complexity) is resilient to\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Omega (\\sqrt {n} \\cdot \\log ^3 n)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    adaptive corruptions. Namely, majority is the\n                    <jats:italic toggle=\"yes\">optimal<\/jats:italic>\n                    coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).\n                  <\/jats:p>","DOI":"10.1145\/3814954","type":"journal-article","created":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T10:55:35Z","timestamp":1778756135000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3167-3294","authenticated-orcid":false,"given":"Iftach","family":"Haitner","sequence":"first","affiliation":[{"name":"The Blavatnik School of Computer Science, Tel Aviv University","place":["Tel Aviv, Israel"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8395-8878","authenticated-orcid":false,"given":"Yonatan","family":"Karidi-Heller","sequence":"additional","affiliation":[{"name":"The Blavatnik School of Computer Science, Tel Aviv University","place":["Tel Aviv, Israel"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303199"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222030"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00084"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.15"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2979676"},{"key":"e_1_3_2_7_2","volume-title":"Proceedings of the Annual International Cryptology Conference (CRYPTO)","author":"Berman Itay","year":"2020","unstructured":"Itay Berman, Iftach Haitner, and Eliad Tsfadia. 2020. A tight parallel-repetition theorem for random-terminating interactive arguments. In Proceedings of the Annual International Cryptology Conference (CRYPTO)."},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","unstructured":"Manuel Blum. 1983. How to exchange (secret) keys (extended abstract). In Proceedings of the 15th Annual ACM Symposium on Theory of Computing. 440\u2013447.","DOI":"10.1145\/800061.808775"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307182"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_25"},{"key":"e_1_3_2_11_2","unstructured":"Yevgeniy Dodis. 2006. Fault-Tolerant Leader Election and Collective Coin-Flipping in the Full Information Model. (2006). Retrieved from https:\/\/cs.nyu.edu\/dodis\/ps\/cf-survey.pdf"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.21"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.811927"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_53"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/100810630"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/120887631"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11799-2_1"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3639454"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2837019"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125896"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70503-3_8"},{"key":"e_1_3_2_23_2","first-page":"581","volume-title":"Proceedings of the Algorithmic Learning Theory","author":"Mahloujifar Saeed","year":"2019","unstructured":"Saeed Mahloujifar and Mohammad Mahmoody. 2019. Can adversarially robust learning leveragecomputational hardness?. In Proceedings of the Algorithmic Learning Theory. 581\u2013609."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.64"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376007"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0402020"},{"key":"e_1_3_2_27_2","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC)","author":"Kalai Yael Tauman","year":"2018","unstructured":"Yael Tauman Kalai, Ilan Komargodski, and Ran Raz. 2018. A lower bound for adaptively-secure collective coin-flipping protocols. In Proceedings of the International Symposium on Distributed Computing (DISC)."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3814954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T13:59:19Z","timestamp":1781618359000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3814954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,16]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3814954"],"URL":"https:\/\/doi.org\/10.1145\/3814954","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,16]]},"assertion":[{"value":"2024-11-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-11","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}