{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:58:32Z","timestamp":1778065112586,"version":"3.51.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,2,21]],"date-time":"2015-02-21T00:00:00Z","timestamp":1424476800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s00145-015-9199-z","type":"journal-article","created":{"date-parts":[[2015,2,20]],"date-time":"2015-02-20T15:51:37Z","timestamp":1424447497000},"page":"491-513","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["An Optimally Fair Coin Toss"],"prefix":"10.1007","volume":"29","author":[{"given":"Tal","family":"Moran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moni","family":"Naor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,21]]},"reference":[{"key":"9199_CR1","unstructured":"D.\u00a0Aharonov, A.\u00a0Ta-Shma, U.V. Vazirani, A.C. Yao, Quantum bit escrow, in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (2000), pp. 705\u2013714"},{"key":"9199_CR2","doi-asserted-by":"crossref","unstructured":"N.\u00a0Alon, M.\u00a0Naor, Coin-flipping games immune against linear-sized coalitions. SIAM J. Comput.\n                           22(2), 403\u2013417 (1993)","DOI":"10.1137\/0222030"},{"key":"9199_CR3","doi-asserted-by":"crossref","unstructured":"A.\u00a0Ambainis, A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci.\n                           68(2), 398\u2013416 (2004)","DOI":"10.1016\/j.jcss.2003.07.010"},{"key":"9199_CR4","unstructured":"A.\u00a0Ambainis, H.\u00a0Buhrman, Y.\u00a0Dodis, H.\u00a0Rohrig, Multiparty quantum coin flipping, in Proceedings of the 19th Annual IEEE Conference on Computational Complexity (2004), pp. 250\u2013259"},{"key":"9199_CR5","unstructured":"B.\u00a0Averbuch, M.\u00a0Blum, B.\u00a0Chor, S.\u00a0Goldwasser, S.\u00a0Micali, How to implement Bracha\u2019s\u00a0\n                    \n                      \n                    \n                    $${O}(\\log n)$$\n                    \n                      \n                        \n                          O\n                          (\n                          log\n                          n\n                          )\n                        \n                      \n                    \n                  \u00a0byzantine agreement algorithm. Manuscript (1985)"},{"key":"9199_CR6","unstructured":"A.\u00a0Beimel, Y.\u00a0Lindell, E.\u00a0Omri, I.\u00a0Orlov. \n                    \n                      \n                    \n                    $$1\/p$$\n                    \n                      \n                        \n                          1\n                          \/\n                          p\n                        \n                      \n                    \n                  -secure multiparty computation without honest majority and the best of both worlds, in Advances in Cryptology\u2014CRYPTO \u201911 (2011), pp. 277\u2013296"},{"key":"9199_CR7","unstructured":"A.\u00a0Beimel, E.\u00a0Omri, I.\u00a0Orlov, Protocols for multiparty coin toss with dishonest majority, in Advances in Cryptology\u2014CRYPTO \u201910 (2010), pp. 538\u2013557"},{"key":"9199_CR8","unstructured":"M.\u00a0Bellare, P.\u00a0Rogaway, Code-based game-playing proofs and the security of triple encryption. Cryptology ePrint Archive, Report 2004\/331 (2004). \n                    http:\/\/eprint.iacr.org\/2004\/331.pdf"},{"key":"9199_CR9","unstructured":"M.\u00a0Ben-Or, S.\u00a0Goldwasser, A.\u00a0Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (1988), pp. 1\u201310"},{"key":"9199_CR10","unstructured":"M.\u00a0Ben-Or, N.\u00a0Linial, Collective coin flipping. Adv. Comput. Res. Randomness Comput.\n                           5, 91\u2013115 (1989)"},{"key":"9199_CR11","unstructured":"I.\u00a0Berman, I.\u00a0Haitner, A.\u00a0Tentes, Coin flipping of any constant bias implies one-way functions, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (2014), pp. 398\u2013407"},{"key":"9199_CR12","unstructured":"M.\u00a0Blum, Coin flipping by telephone\u2014A protocol for solving impossible problems, in Proceedings of the 25th IEEE Computer Society International Conference (1982), pp. 133\u2013137"},{"key":"9199_CR13","doi-asserted-by":"crossref","unstructured":"R.\u00a0Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptol.\n                           13(1), 143\u2013202 (2000)","DOI":"10.1007\/s001459910006"},{"key":"9199_CR14","unstructured":"R. Cleve, Limits on the security of coin flips when half the processors are faulty, in Proceedings of the 18th Annual ACM Symposium on Theory of Computing (1986). pp. 364\u2013369"},{"key":"9199_CR15","unstructured":"R.\u00a0Cleve, R.\u00a0Impagliazzo, Martingales, collective coin flipping and discrete control processes. \n                    http:\/\/www.cpsc.ucalgary.ca\/~cleve\/pubs\/martingales.ps\n                    \n                   (1993)"},{"key":"9199_CR16","unstructured":"D.\u00a0Dachman-Soled, Y.\u00a0Lindell, M.\u00a0Mahmoody, T.\u00a0Malkin, On the black-box complexity of optimally-fair coin tossing, in Proceedings of the 8th Theory of Cryptography Conference (2011), pp. 450\u2013467"},{"key":"9199_CR17","unstructured":"D.\u00a0Dachman-Soled, M.\u00a0Mahmoody, T.\u00a0Malkin, Can optimally-fair coin tossing be based on one-way functions? in Proceedings of the 11th Theory of Cryptography Conference (2014), pp. 217\u2013239"},{"key":"9199_CR18","unstructured":"U.\u00a0Feige, Noncryptographic selection protocols, in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (1999), pp. 142\u2013153"},{"key":"9199_CR19","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography\u2014Volume 2: Basic Applications. (Cambridge University Press, Cambridge, 2004)"},{"key":"9199_CR20","unstructured":"S.D. Gordon, C.\u00a0Hazay, J.\u00a0Katz, Y.\u00a0Lindell, Complete fairness in secure two-party computation, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (2008), pp. 413\u2013422"},{"key":"9199_CR21","unstructured":"S.D. Gordon, J.\u00a0Katz, Rational secret sharing, revisited, in Proceedings on the 5th International Conference on Security and Cryptography for Networks (2006), pp. 229\u2013241"},{"key":"9199_CR22","doi-asserted-by":"crossref","unstructured":"S.D. Gordon, J.\u00a0Katz, Partial fairness in secure two-party computation. J. Cryptol.\n                           25(1), 14\u201340 (2012)","DOI":"10.1007\/s00145-010-9079-5"},{"key":"9199_CR23","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, E.\u00a0Omri, Coin flipping with constant bias implies one-way functions. SIAM J. Comput.\n                           43(2), 389\u2013409 (2014)","DOI":"10.1137\/120887631"},{"key":"9199_CR24","unstructured":"I.\u00a0Haitner, E.\u00a0Tsfadia, An almost-optimally fair three-party coin-flipping protocol, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (2014), pp. 408\u2013416"},{"key":"9199_CR25","unstructured":"J.Y. Halpern, V.\u00a0Teague, Rational secret sharing and multiparty computation, in Proceedings of the 36th Annual ACM Symposium on Theory of Computing (2004), pp. 623\u2013632"},{"key":"9199_CR26","doi-asserted-by":"crossref","unstructured":"J.\u00a0H\u00e5stad, R.\u00a0Impagliazzo, L.A. Levin, M.\u00a0Luby, A pseudorandom generator from any one-way function. SIAM J. Comput.\n                           28(4), 1364\u20131396 (1999)","DOI":"10.1137\/S0097539793244708"},{"key":"9199_CR27","doi-asserted-by":"crossref","unstructured":"C.\u00a0Hazay, Y.\u00a0Lindell, Efficient Secure Two-Party Protocols\u2014Techniques and Constructions (Springer, Berlin, 2010)","DOI":"10.1007\/978-3-642-14303-8"},{"key":"9199_CR28","unstructured":"R.\u00a0Impagliazzo, M.\u00a0Luby, One-way functions are essential for complexity based cryptography, in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (1989), pp. 230\u2013235"},{"key":"9199_CR29","unstructured":"J.\u00a0Katz, On achieving the \u201cbest of both worlds\u201d in secure multiparty computation, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (2007), pp. 11\u201320"},{"key":"9199_CR30","unstructured":"G.\u00a0Kol, M.\u00a0Naor, Cryptography and game theory: Designing protocols for exchanging information, in Proceedings of the 5th Theory of Cryptography Conference (2008), pp. 320\u2013339."},{"key":"9199_CR31","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Lindell, Parallel coin-tossing and constant-round secure two-party computation. J. Cryptol.\n                           16(3), 143\u2013184 (2003)","DOI":"10.1007\/s00145-002-0143-7"},{"key":"9199_CR32","unstructured":"H.K. Maji, M.\u00a0Prabhakaran, A.\u00a0Sahai, On the computational complexity of coin flipping, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (2010), pp. 613\u2013622"},{"key":"9199_CR33","unstructured":"T.\u00a0Moran, M.\u00a0Naor, Basing cryptographic protocols on tamper-evident seals, in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, (2005), pp. 285\u2013297"},{"key":"9199_CR34","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naor, Bit commitment using pseudorandomness. J. Cryptol.\n                           4(2), 151\u2013158 (1991)","DOI":"10.1007\/BF00196774"},{"key":"9199_CR35","doi-asserted-by":"crossref","unstructured":"A.\u00a0Russell, D.\u00a0Zuckerman, Perfect information leader election in \n                    \n                      \n                    \n                    $$\\log ^*n + {O}(1)$$\n                    \n                      \n                        \n                          \n                            log\n                            \u2217\n                          \n                          n\n                          +\n                          O\n                          \n                            (\n                            1\n                            )\n                          \n                        \n                      \n                    \n                   rounds. J. Comput. Syst. Sci.\n                           63(4), 612\u2013626 (2001)","DOI":"10.1006\/jcss.2001.1776"},{"key":"9199_CR36","doi-asserted-by":"crossref","unstructured":"M.\u00a0Saks, A robust noncryptographic protocol for collective coin flipping. SIAM J. Discrete Math.\n                           2(2), 240\u2013244 (1989)","DOI":"10.1137\/0402020"},{"key":"9199_CR37","doi-asserted-by":"crossref","unstructured":"M.N. Wegman, L. Carter, New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci.\n                           22(3), 265\u2013279 (1981)","DOI":"10.1016\/0022-0000(81)90033-7"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9199-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-015-9199-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9199-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9199-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:23:37Z","timestamp":1586334217000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-015-9199-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,21]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9199"],"URL":"https:\/\/doi.org\/10.1007\/s00145-015-9199-z","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,21]]},"assertion":[{"value":"17 May 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2015","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}