{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T20:15:53Z","timestamp":1770840953169,"version":"3.50.1"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T00:00:00Z","timestamp":1762387200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T00:00:00Z","timestamp":1762387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004375","name":"Tel Aviv University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004375","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2026,1]]},"abstract":"Abstract<\/jats:title>\n \n In a multi-party\n fair<\/jats:italic>\n coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some adversarial parties try to bias the output. In this work, we focus on the case of an arbitrary number of corrupted parties. Cleve [20] [STOC 1986] has shown that in\n any<\/jats:italic>\n such\n m<\/jats:italic>\n -round coin-flipping protocol, the corrupted parties can bias the honest parties\u2019 common output bit by\n \n \n $$\\Theta (1\/m)$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . For more than two decades, however, the best-known coin-flipping protocol was the one of Awerbuch, Blum, Chor, Goldwasser, and Micali [10] [Manuscript 1985], who presented a\n t<\/jats:italic>\n -party,\n m<\/jats:italic>\n -round protocol with bias\n \n \n $$\\Theta (t\/\\sqrt{m})$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n t<\/mml:mi>\n \/<\/mml:mo>\n \n m<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . This was changed by the breakthrough result of Moran, Naor, and Segev [51] [Journal of Cryptology 2016], who constructed an\n m<\/jats:italic>\n -round,\n two<\/jats:italic>\n -party coin-flipping protocol with optimal bias\n \n \n $$\\Theta (1\/m)$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . More recently, Haitner and Tsfadia [37] [SIAM Journal on Computing 2017] constructed an\n m<\/jats:italic>\n -round,\n three<\/jats:italic>\n -party coin-flipping protocol with bias\n \n \n $$O(\\log ^3m \/ m)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:msup>\n m<\/mml:mi>\n \/<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Still for the case of more than three parties, the best-known protocol remained the\n \n \n $$\\Theta (t\/\\sqrt{m})$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n t<\/mml:mi>\n \/<\/mml:mo>\n \n m<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -bias protocol of [10]. We make a step toward eliminating the above gap, presenting a\n t<\/jats:italic>\n -party,\n m<\/jats:italic>\n -round coin-flipping protocol, with bias\n \n \n $$O\\left( \\frac{t^4 \\cdot 2^t \\cdot \\sqrt{\\log m}}{m^{1\/2+1\/(2^{t-1}-2)}}\\right) $$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \n \n \n \n t<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n 2<\/mml:mn>\n t<\/mml:mi>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n \n log<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n <\/mml:mrow>\n \n m<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n +<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n \n t<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n -<\/mml:mo>\n 2<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for any\n \n \n $$t\\le \\tfrac{1}{2} \\cdot \\operatorname {loglog}m$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n \u2264<\/mml:mo>\n \n \n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mstyle>\n \u00b7<\/mml:mo>\n loglog<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . This improves upon the\n \n \n $$\\Theta (t\/\\sqrt{m})$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n t<\/mml:mi>\n \/<\/mml:mo>\n \n m<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -bias protocol of [10], and in particular, for\n \n \n $$t\\in O(1)$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n \u2208<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n it is an\n \n \n $$1\/m^{\\frac{1}{2} + \\Theta (1)}$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n \/<\/mml:mo>\n \n m<\/mml:mi>\n \n \n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:mfrac>\n +<\/mml:mo>\n \u0398<\/mml:mi>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -bias protocol. For the three-party case, it is an\n \n \n $$O(\\sqrt{\\log m}\/m)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n log<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n \/<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -bias protocol, improving over the\n \n \n $$O(\\log ^3m \/ m)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:msup>\n m<\/mml:mi>\n \/<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -bias protocol of [37]. Our protocol generalizes that of [37], by presenting an appropriate \u201crecovery protocol\u201d for the remaining parties to interact in, in the case that some parties abort or are caught cheating ([37] only presented a two-party recovery protocol, which limits their final protocol to handle three parties). We prove the fairness of the new protocol by presenting a new paradigm for analyzing fairness of coin-flipping protocols; the claimed fairness is proved by mapping the set of adversarial strategies that try to bias the honest parties\u2019 outcome in the protocol to the set of the feasible solutions of a linear program. The gain each strategy achieves is the value of the corresponding solution. We then bound the optimal value of the linear program by constructing a feasible solution to its dual.\n <\/jats:p>","DOI":"10.1007\/s00145-025-09561-6","type":"journal-article","created":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T16:38:17Z","timestamp":1762447097000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fair Coin Flipping: Tighter Analysis and the Many-Party Case"],"prefix":"10.1007","volume":"39","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[]},{"given":"Iftach","family":"Haitner","sequence":"additional","affiliation":[]},{"given":"Nissan","family":"Levi","sequence":"additional","affiliation":[]},{"given":"Eliad","family":"Tsfadia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,11,6]]},"reference":[{"key":"9561_CR1","unstructured":"M. Abramowitz, I.A. Stegun, editors. Handbook of Mathematical Functions. Dover Publications, (1964)"},{"key":"9561_CR2","doi-asserted-by":"crossref","unstructured":"D.\u00a0Aharonov, A.\u00a0Ta-Shma, U.\u00a0Vazirani, A.C. Yao, Quantum bit escrow. In STOC: ACM Symposium on Theory of Computing (STOC), (2000)","DOI":"10.1145\/335305.335404"},{"key":"9561_CR3","doi-asserted-by":"crossref","unstructured":"W.\u00a0Aiello, Y.\u00a0Ishai, O.\u00a0Reingold, Priced oblivious transfer: How to sell digital goods. In Advances in Cryptology \u2013 EUROCRYPT 2001, (2001)","DOI":"10.1007\/3-540-44987-6_8"},{"key":"9561_CR4","doi-asserted-by":"crossref","unstructured":"B.\u00a0Alon, E.\u00a0Omri, Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious. Cryptology ePrint Archive, Report 2016\/800, (2016). http:\/\/eprint.iacr.org\/2016\/800","DOI":"10.1007\/978-3-662-53641-4_13"},{"key":"9561_CR5","doi-asserted-by":"crossref","unstructured":"N.\u00a0Alon, M.\u00a0Naor, Coin-flipping games immune against linear-sized coalitions. SIAM Journal on Computing, pp. 46\u201354, (1993)","DOI":"10.1109\/FSCS.1990.89523"},{"issue":"2","key":"9561_CR6","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1016\/j.jcss.2003.07.010","volume":"68","author":"A Ambainis","year":"2004","unstructured":"A.\u00a0Ambainis, A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci.68(2), 398\u2013416 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9561_CR7","doi-asserted-by":"crossref","unstructured":"A.\u00a0Ambainis, H.\u00a0Buhrman, Y.\u00a0Dodis, H.\u00a0R\u00f6hrig, Multiparty quantum coin flipping. In Proceedings of the 18th Annual IEEE Conference on Computational Complexity, pages 250\u2013259, (2004)","DOI":"10.1109\/CCC.2004.1313848"},{"key":"9561_CR8","doi-asserted-by":"publisher","unstructured":"G.\u00a0Asharov, Towards characterizing complete fairness in secure two-party computation. In Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings, pp. 291\u2013316, (2014) https:\/\/doi.org\/10.1007\/978-3-642-54242-8_13","DOI":"10.1007\/978-3-642-54242-8_13"},{"key":"9561_CR9","doi-asserted-by":"crossref","unstructured":"G.\u00a0Asharov, A.\u00a0Beimel, N.\u00a0Makriyannis, E.\u00a0Omri. Complete characterization of fairness in secure two-party computation of boolean functions. In Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I, pp. 199\u2013228, (2015)","DOI":"10.1007\/978-3-662-46494-6_10"},{"key":"9561_CR10","unstructured":"B.\u00a0Awerbuch, M.\u00a0Blum, B.\u00a0Chor, S.\u00a0Goldwasser, and S.\u00a0Micali. How to implement bracha\u2019s o (log n) byzantine agreement algorithm. unpublished, (1985)"},{"key":"9561_CR11","doi-asserted-by":"crossref","unstructured":"D.\u00a0Beaver, S.\u00a0Micali, P.\u00a0Rogaway, The round complexity of secure protocols. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 503\u2013513, (1990)","DOI":"10.1145\/100216.100287"},{"key":"9561_CR12","doi-asserted-by":"crossref","unstructured":"A.\u00a0Beimel, E.\u00a0Omri, I.\u00a0Orlov, Protocols for multiparty coin toss with dishonest majority. In Advances in Cryptology \u2013 CRYPTO 2010, volume 6223, pp. 538\u2013557, (2010)","DOI":"10.1007\/978-3-642-14623-7_29"},{"key":"9561_CR13","doi-asserted-by":"crossref","unstructured":"A.\u00a0Beimel, Y.\u00a0Lindell, E.\u00a0Omri, I.\u00a0Orlov, 1\/p-secure multiparty computation without honest majority and the best of both worlds. In Advances in Cryptology \u2013 CRYPTO 2011, pp. 277\u2013296 (2011)","DOI":"10.1007\/978-3-642-22792-9_16"},{"issue":"4","key":"9561_CR14","doi-asserted-by":"publisher","first-page":"1126","DOI":"10.1137\/18M1210782","volume":"51","author":"A Beimel","year":"2022","unstructured":"A.\u00a0Beimel, I.\u00a0Haitner, N.\u00a0Makriyannis, E.\u00a0Omri, Tighter bounds on multiparty coin flipping via augmented weak martingales and differentially private sampling. sicomp. 51(4), 1126\u20131171 (2022)","journal-title":"sicomp."},{"key":"9561_CR15","unstructured":"M.\u00a0Ben-Or, N.\u00a0Linial, Collective coin flipping. ADVCR: Advances in Computing Research, 5, (1989)"},{"key":"9561_CR16","doi-asserted-by":"crossref","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 (STOC), (1988)","DOI":"10.1145\/62212.62213"},{"key":"9561_CR17","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 (STOC), pp. 817\u2013836, (2014)"},{"key":"9561_CR18","doi-asserted-by":"crossref","unstructured":"M.\u00a0Blum, How to exchange (secret) keys. ACM Transactions on Computer Systems, (1983)","DOI":"10.1145\/800061.808775"},{"issue":"1","key":"9561_CR19","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"R.\u00a0Canetti, Security and composition of multiparty cryptographic protocols. Journal of Cryptology. 13(1), 143\u2013202 (2000)","journal-title":"J. Cryptol."},{"key":"9561_CR20","doi-asserted-by":"crossref","unstructured":"R.\u00a0Cleve, Limits on the security of coin flips when half the processors are faulty. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 364\u2013369, (1986)","DOI":"10.1145\/12130.12168"},{"key":"9561_CR21","unstructured":"R.\u00a0Cleve, R.\u00a0Impagliazzo, Martingales, collective coin flipping and discrete control processes. Manuscript, (1993) URL https:\/\/pdfs.semanticscholar.org\/7c7f\/244d2ef064d75b3d23c88472ee1226461695.pdf."},{"key":"9561_CR22","doi-asserted-by":"crossref","unstructured":"R.\u00a0Cohen, I.\u00a0Haitner, E.\u00a0Omri, L.\u00a0Rotem, Characterization of secure multiparty computation without broadcast. In Theory of Cryptography, 13th Theory of Cryptography Conference, TCC 2016a, pp. 596\u2013616, (2016)","DOI":"10.1007\/978-3-662-49096-9_25"},{"key":"9561_CR23","doi-asserted-by":"crossref","unstructured":"D.\u00a0Dachman-Soled, Y.\u00a0Lindell, M.\u00a0Mahmoody, T.\u00a0Malkin, On the black-box complexity of optimally-fair coin tossing. In tcc11, pp. 450\u2013467, (2011)","DOI":"10.1007\/978-3-642-19571-6_27"},{"key":"9561_CR24","doi-asserted-by":"crossref","unstructured":"D.\u00a0Dachman-Soled, M.\u00a0Mahmoody, T.\u00a0Malkin, Can optimally-fair coin tossing be based on one-way functions? In tcc14, pp. 217\u2013239, (2014)","DOI":"10.1007\/978-3-642-54242-8_10"},{"issue":"6","key":"9561_CR25","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1145\/3812.3818","volume":"28","author":"S Even","year":"1985","unstructured":"S.\u00a0Even, O.\u00a0Goldreich, A.\u00a0Lempel, A randomized protocol for signing contracts. Communications of the ACM. 28(6), 637\u2013647 (1985)","journal-title":"Commun. ACM"},{"key":"9561_CR26","unstructured":"U.\u00a0Feige, Noncryptographic selection protocols. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), (1999)"},{"key":"9561_CR27","unstructured":"T.S. Ferguson, Optimal stopping and applications (Online book), (2006). www.math.ucla.edu\/~tom\/Stopping\/contents.html"},{"key":"9561_CR28","doi-asserted-by":"crossref","unstructured":"C.\u00a0Gentry, C.\u00a0Peikert, V.\u00a0Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 197\u2013206, (2008)","DOI":"10.1145\/1374376.1374407"},{"key":"9561_CR29","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography \u2013 VOLUME 2: Basic Applications. Cambridge University Press, (2004)","DOI":"10.1017\/CBO9780511721656"},{"key":"9561_CR30","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, S.\u00a0Micali, A.\u00a0Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 218\u2013229, (1987)","DOI":"10.1145\/28395.28420"},{"key":"9561_CR31","doi-asserted-by":"crossref","unstructured":"S.\u00a0Goldwasser, Y.T. Kalai, S.\u00a0Park, Adaptively secure coin-flipping, revisited. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, volume 9135, pp. 663\u2013674, (2015)","DOI":"10.1007\/978-3-662-47666-6_53"},{"key":"9561_CR32","first-page":"157","volume":"2011","author":"SD Gordon","year":"2010","unstructured":"S.D. Gordon, J.\u00a0Katz, Partial fairness in secure two-party computation. In Advances in Cryptology \u2013 EUROCRYPT 2011, pages 157\u2013176, (2010)","journal-title":"In Advances in Cryptology - EUROCRYPT"},{"issue":"6","key":"9561_CR33","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/2049697.2049698","volume":"58","author":"SD Gordon","year":"2011","unstructured":"S.D. Gordon, C.\u00a0Hazay, J.\u00a0Katz, Y.\u00a0Lindell, Complete fairness in secure two-party computation. Journal of the ACM, 58(6), 24 (2011)","journal-title":"J. ACM"},{"key":"9561_CR34","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, Implementing oblivious transfer using collection of dense trapdoor permutations. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, pp. 394\u2013409, (2004)","DOI":"10.1007\/978-3-540-24638-1_22"},{"key":"9561_CR35","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, Y.\u00a0Karidi-Heller, A tight lower bound on adaptively secure full-information coin flip. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pp. 1268\u20131276, (2020)","DOI":"10.1109\/FOCS46700.2020.00120"},{"key":"9561_CR36","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, E.\u00a0Omri, Coin Flipping with Constant Bias Implies One-Way Functions. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 110\u2013119, (2011)","DOI":"10.1109\/FOCS.2011.29"},{"issue":"2","key":"9561_CR37","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1137\/15M1009147","volume":"46","author":"I Haitner","year":"2017","unstructured":"I.\u00a0Haitner, E.\u00a0Tsfadia, An almost-optimally fair three-party coin-flipping protocol. SIAM Journal on Computing. 46(2), 479\u2013542 (2017)","journal-title":"SIAM J. Comput."},{"key":"9561_CR38","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, M.\u00a0Nguyen, S.\u00a0J. Ong, O.\u00a0Reingold, S.\u00a0Vadhan, Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM Journal on Computing, pages 1153\u20131218, (2009a)","DOI":"10.1137\/080725404"},{"key":"9561_CR39","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, O.\u00a0Reingold, S.\u00a0Vadhan, H.\u00a0Wee, Inaccessible entropy. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 611\u2013620, (2009b)","DOI":"10.1145\/1536414.1536497"},{"key":"9561_CR40","doi-asserted-by":"crossref","unstructured":"I.\u00a0Haitner, N.\u00a0Makriyannis, E.\u00a0Omri. On the complexity of fair coin flipping. www.cs.tau.ac.il\/~iftachh\/papers\/CFtoKA\/TwoPartyCoinFlipToKA.pdf, (2018) Manuscript.","DOI":"10.1007\/978-3-030-03807-6_20"},{"key":"9561_CR41","doi-asserted-by":"crossref","unstructured":"J.\u00a0H\u00e5stad, R.\u00a0Impagliazzo, L.A. Levin, M.\u00a0Luby, A pseudorandom generator from any one-way function. SIAM Journal on Computing, pp. 1364\u20131396, (1999)","DOI":"10.1137\/S0097539793244708"},{"key":"9561_CR42","doi-asserted-by":"crossref","unstructured":"W.\u00a0Hoeffding, Probability inequalities for sums of bounded random variables, (1963)","DOI":"10.1080\/01621459.1963.10500830"},{"key":"9561_CR43","doi-asserted-by":"crossref","unstructured":"R.\u00a0Impagliazzo, M.\u00a0Luby, One-way functions are essential for complexity based cryptography. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 230\u2013235, (1989)","DOI":"10.1109\/SFCS.1989.63483"},{"key":"9561_CR44","unstructured":"T.Y. Kalai, I.\u00a0Komargodski, R.\u00a0Raz, A lower bound for adaptively-secure collective coin-flipping protocols. DISC. 34:1\u201334:16 (2018)"},{"key":"9561_CR45","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Kalai, Smooth projective hashing and two-message oblivious transfer. In Advances in Cryptology \u2013 EUROCRYPT 2005, (2005)","DOI":"10.1007\/11426639_5"},{"key":"9561_CR46","doi-asserted-by":"crossref","unstructured":"J.\u00a0Katz, On achieving the \u201cbest of both worlds\u201d in secure multiparty computation. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 11\u201320, (2007)","DOI":"10.1145\/1250790.1250793"},{"key":"9561_CR47","doi-asserted-by":"crossref","unstructured":"H.K. Maji, M.\u00a0Wang, Black-box use of one-way functions is useless for optimal fair coin-tossing. In Advances in Cryptology \u2013 CRYPTO 2020, volume 12171, pp. 593\u2013617, (2020)","DOI":"10.1007\/978-3-030-56880-1_21"},{"key":"9561_CR48","first-page":"33","volume":"2021","author":"HK Maji","year":"2021","unstructured":"H.K. Maji, M.\u00a0Wang, Computational hardness of optimal fair computation: Beyond minicrypt. In Advances in Cryptology \u2013 CRYPTO 2021, pages 33\u201363, (2021)","journal-title":"In Advances in Cryptology \u2013 CRYPTO"},{"key":"9561_CR49","doi-asserted-by":"crossref","unstructured":"H.\u00a0K. Maji, M.\u00a0Prabhakaran, A.\u00a0Sahai, On the Computational Complexity of Coin Flipping. In Proceedings of the 51th Annual Symposium on Foundations of Computer Science (FOCS), pp. 613\u2013622, (2010)","DOI":"10.1109\/FOCS.2010.64"},{"key":"9561_CR50","doi-asserted-by":"crossref","unstructured":"T.\u00a0Moran, M.\u00a0Naor, Basing cryptographic protocols on tamper-evident seals. In ICALP: Annual International Colloquium on Automata, Languages and Programming, (2005)","DOI":"10.1007\/11523468_24"},{"issue":"3","key":"9561_CR51","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s00145-015-9199-z","volume":"29","author":"T Moran","year":"2016","unstructured":"T.\u00a0Moran, M.\u00a0Naor, G.\u00a0Segev, An optimally fair coin toss. Journal of Cryptology, 29(3), 491\u2013513 (2016)","journal-title":"J. Cryptol."},{"key":"9561_CR52","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naor, Bit commitment using pseudorandomness. Journal of Cryptology, pp. 151\u2013158, (1991)","DOI":"10.1007\/BF00196774"},{"key":"9561_CR53","unstructured":"M.\u00a0Naor, B.\u00a0Pinkas, Efficient oblivious transfer protocols. In SODA, pp. 448\u2013457, (2001)"},{"key":"9561_CR54","doi-asserted-by":"crossref","unstructured":"R.\u00a0Pass, Bounded-concurrent secure multi-party computation with a dishonest majority. In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201904, pp. 232\u2013241, (2004)","DOI":"10.1145\/1007352.1007393"},{"key":"9561_CR55","doi-asserted-by":"crossref","unstructured":"A.\u00a0Russell, D.\u00a0Zuckerman, Perfect information leader election in log* n + 0 (1) rounds. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 576\u2013583, (1999)","DOI":"10.1109\/SFCS.1998.743508"},{"key":"9561_CR56","doi-asserted-by":"crossref","unstructured":"M.\u00a0Saks, A robust noncryptographic protocol for collective coin flipping. SIJDM: SIAM Journal on Discrete Mathematics, 2, (1989)","DOI":"10.1137\/0402020"},{"key":"9561_CR57","unstructured":"M.\u00a0Scala, Hypergeometric tail inequalities: ending the insanity. arXiv preprint arXiv:1311.5939, (2009)"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09561-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-025-09561-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09561-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T20:00:15Z","timestamp":1770840015000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-025-09561-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,6]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["9561"],"URL":"https:\/\/doi.org\/10.1007\/s00145-025-09561-6","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,6]]},"assertion":[{"value":"20 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}