{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T22:42:02Z","timestamp":1778798522217,"version":"3.51.4"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,13]],"date-time":"2018-03-13T00:00:00Z","timestamp":1520899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100005386","name":"Israeli Centers of Research Excellence","doi-asserted-by":"crossref","award":["4\/11 (http:\/\/www.icore-algo.org.il\/)"],"award-info":[{"award-number":["4\/11 (http:\/\/www.icore-algo.org.il\/)"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"crossref"}]},{"name":"United states - Israel Binational Science Foundation","award":["2010196"],"award-info":[{"award-number":["2010196"]}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100021796","name":"Check Point Institute for Information Security","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021796","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1076\/11 G1"],"award-info":[{"award-number":["1076\/11 G1"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000183","name":"U.S. Army Research Office","doi-asserted-by":"crossref","award":["W911NF-15-C-0226 and W911NF-15-C-0236"],"award-info":[{"award-number":["W911NF-15-C-0226 and W911NF-15-C-0236"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1413920 and CNS-1350619"],"award-info":[{"award-number":["CNS-1413920 and CNS-1350619"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>\n            We show that the existence of a coin-flipping protocol safe against\n            <jats:italic>any<\/jats:italic>\n            nontrivial constant bias (e.g., .499) implies the existence of one-way functions. This improves upon a result of Haitner and Omri (FOCS\u201911), who proved this implication for protocols with bias \u221a 2\u22121\/2 \u2212\n            <jats:italic>o<\/jats:italic>\n            (1) \u2248 .207. Unlike the result of Haitner and Omri, our result also holds for\n            <jats:italic>weak<\/jats:italic>\n            coin-flipping protocols.\n          <\/jats:p>","DOI":"10.1145\/2979676","type":"journal-article","created":{"date-parts":[[2018,3,14]],"date-time":"2018-03-14T12:34:20Z","timestamp":1521030860000},"page":"1-95","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Coin Flipping of\n            <i>Any<\/i>\n            Constant Bias Implies One-Way Functions"],"prefix":"10.1145","volume":"65","author":[{"given":"Itay","family":"Berman","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iftach","family":"Haitner","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aris","family":"Tentes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"B. Averbuch M. Blum B. Chor S. Goldwasser and S. Micali. 1985. How to implement Bracha\u2019s O(log n) Byzantine agreement algorithm. Unpublished manuscript.  B. Averbuch M. Blum B. Chor S. Goldwasser and S. Micali. 1985. How to implement Bracha\u2019s O (log n ) Byzantine agreement algorithm. Unpublished manuscript."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"A. Beimel E. Omri and I. Orlov. 2010. Protocols for multiparty coin toss with dishonest majority. In Advances in Cryptology (CRYPTO\u201910). 538--557.   A. Beimel E. Omri and I. Orlov. 2010. Protocols for multiparty coin toss with dishonest majority. In Advances in Cryptology (CRYPTO\u201910). 538--557.","DOI":"10.1007\/978-3-642-14623-7_29"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591845"},{"key":"e_1_2_1_4_1","unstructured":"M. Blum. 1981. Coin flipping by telephone. In Advances in Cryptology (CRYPTO\u201981). 11--15.  M. Blum. 1981. Coin flipping by telephone. In Advances in Cryptology (CRYPTO\u201981). 11--15."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.71"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12168"},{"key":"e_1_2_1_7_1","unstructured":"R. Cleve and R. Impagliazzo. 1993. Martingales collective coin flipping and discrete control processes (Extended Abstract). Retrieved from http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi&equals;10.1.1.51.1797.  R. Cleve and R. Impagliazzo. 1993. Martingales collective coin flipping and discrete control processes (Extended Abstract). Retrieved from http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi&equals;10.1.1.51.1797."},{"key":"e_1_2_1_8_1","volume-title":"8th Theory of Cryptography Conference (TCC\u201911)","volume":"6597","author":"Dachman-Soled D."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"O. Goldreich S. Goldwasser and S. Micali. 1984. On the cryptographic applications of random functions. In Advances in Cryptology (CRYPTO\u201984). 276--288.   O. Goldreich S. Goldwasser and S. Micali. 1984. On the cryptographic applications of random functions. In Advances in Cryptology (CRYPTO\u201984). 276--288.","DOI":"10.1007\/3-540-39568-7_22"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/080725404"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.29"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_15_1","unstructured":"R. Impagliazzo. Pseudo-random generators for cryptography and for randomized algorithms. Ph.D. Thesis. Retrieved from http:\/\/cseweb.ucsd.edu\/russell\/format.ps.  R. Impagliazzo. Pseudo-random generators for cryptography and for randomized algorithms. Ph.D. Thesis. Retrieved from http:\/\/cseweb.ucsd.edu\/russell\/format.ps."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_2_1_17_1","unstructured":"A. Y. Kitaev. 2003. Quantum coin-flipping. (2003). Presentation at the 6th Workshop on Quantum Information Processing (QIP\u201903).  A. Y. Kitaev. 2003. Quantum coin-flipping. (2003). Presentation at the 6th Workshop on Quantum Information Processing (QIP\u201903)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.64"},{"key":"e_1_2_1_19_1","unstructured":"C. Mochon. 2007. Quantum weak coin flipping with arbitrarily small bias. arXiv:0711.4114. (2007).  C. Mochon. 2007. Quantum weak coin flipping with arbitrarily small bias. arXiv:0711.4114. (2007)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73011"},{"key":"e_1_2_1_23_1","unstructured":"A. Wayne Roberts and D. E. Varberg. 1973. Convex Functions. Academic Press.  A. Wayne Roberts and D. E. Varberg. 1973. Convex Functions. Academic Press."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100269"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/20284.20312"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2979676","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2979676","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2979676","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:35Z","timestamp":1750222475000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2979676"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,13]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/2979676"],"URL":"https:\/\/doi.org\/10.1145\/2979676","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,13]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}