{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,20]],"date-time":"2024-07-20T05:54:56Z","timestamp":1721454896786},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s00493-020-4147-4","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T17:25:03Z","timestamp":1606757103000},"page":"75-98","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Lower Bound for Adaptively-Secure Collective Coin Flipping Protocols"],"prefix":"10.1007","volume":"41","author":[{"given":"Yael Tauman","family":"Kalai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,30]]},"reference":[{"key":"4147_CR1","volume-title":"How to implement bracha\u2019s o(logn) byzantine agreement algorithm","author":"B Awerbuch","year":"1985","unstructured":"B. Awerbuch, M. Blum, B. Chor, S. Goldwasser and S Micali: How to implement bracha\u2019s o(logn) byzantine agreement algorithm, 1985, unpublished manuscript."},{"key":"4147_CR2","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01303199","volume":"13","author":"M Ajtai","year":"1993","unstructured":"M. Ajtai and N. Llnial: The influence of large coalitions, Combinatorial 13 (1993), 129\u2013145.","journal-title":"Combinatorial"},{"key":"4147_CR3","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/0222030","volume":"22","author":"N Alon","year":"1993","unstructured":"N. Alon and M. Naor: Coin-flipping games immune against linear-sized coalitions, SIAM J. Comput. 22 (1993), 403\u2013417.","journal-title":"SIAM J. Comput."},{"key":"4147_CR4","first-page":"307","volume-title":"Theory of Cryptography - 14th International Conference, TCC 2016-B","author":"B Alon","year":"2016","unstructured":"B. Alon and E. Omri: Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious, in: Theory of Cryptography - 14th International Conference, TCC 2016-B, 307\u2013335, 2016."},{"key":"4147_CR5","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1145\/278298.278304","volume":"45","author":"J Aspnes","year":"1998","unstructured":"J. Aspnes: Lower bounds for distributed coin-flipping and randomized consensus, J. Acm 45 (1998), 415\u2013450.","journal-title":"J. Acm"},{"key":"4147_CR6","first-page":"2580","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"N Buchbinder","year":"2017","unstructured":"N. Buchbinder, I. Haitner, N. Levi and E. Tsfadia: Fair coin nipping: Tighter analysis and the many-party case, in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2580\u20132600. SIAM, 2017."},{"key":"4147_CR7","first-page":"168","volume":"24","author":"A Beimel","year":"2017","unstructured":"A. Beimel, I. Haitner, N. Makriyannis and E. Omri: Tighter bounds on multiparty coin nipping, via augmented weak martingales and di erentially private sampling, Electronic Colloquium on Computational Complexity (ECCC), 24:168, 2017.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"4147_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2979676","volume":"65","author":"I Berman","year":"2018","unstructured":"I. Berman, I. Haitner and A. Tentes: Coin flipping of Any constant bias implies one-way functions, J. Acm, 65 (2018), 1\u201395.","journal-title":"J. Acm"},{"key":"4147_CR9","first-page":"91","volume":"5","author":"M Ben-Or","year":"1989","unstructured":"M. Ben-Or and Nathan Linial: Collective coin flipping, Advances in Computing Research 5 (1989), 91\u2013115.","journal-title":"Advances in Computing Research"},{"key":"4147_CR10","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1145\/357360.357368","volume":"1","author":"M Blum","year":"1983","unstructured":"M. Blum: How to exchange (secret) keys, ACM Trans. Comput. Syst. 1 (1983), 175\u2013193.","journal-title":"ACM Trans. Comput. Syst."},{"key":"4147_CR11","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.1137\/S0097539796307182","volume":"29","author":"R B Boppana","year":"2000","unstructured":"R. B. Boppana and B. O. Narayanan: Perfect-information leader election with optimal resilience, SIAM J. Comput. 29 (2000), 1304\u20131320.","journal-title":"SIAM J. Comput."},{"key":"4147_CR12","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s00145-013-9168-3","volume":"28","author":"A Beimel","year":"2015","unstructured":"A. Beimel, E. Omri and I. Orlov: Protocols for multiparty coin toss with a dishonest majority, J. Cryptology 28 (2015), 551\u2013600.","journal-title":"J. Cryptology"},{"key":"4147_CR13","volume-title":"Martingales, collective coin flipping and discrete control processes (extended abstract)","author":"R Cleve","year":"1993","unstructured":"R. Cleve and R. Impagliazzo: Martingales, collective coin flipping and discrete control processes (extended abstract), 1993, unpublished manuscript."},{"key":"4147_CR14","first-page":"364","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","author":"R Cleve","year":"1986","unstructured":"R. Cleve: Limits on the security of coin flips when half the processors are faulty (extended abstract), in: Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 364\u2013369. ACM, 1986."},{"key":"4147_CR15","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/978-3-642-19571-6_27","volume-title":"Theory of Cryptography - TCC","author":"D Dachman-Soled","year":"2011","unstructured":"D. Dachman-Soled, Y. Llndell, M. Mahmoody and T. Malkin: On the black-box complexity of optimally-fair coin tossing, in: Theory of Cryptography - TCC, 450\u2013467, 2011."},{"key":"4147_CR16","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-642-54242-8_10","volume-title":"Theory of Cryptography - TCC","author":"D Dachman-Soled","year":"2014","unstructured":"D. Dachman-Soled, M. Mahmoody and T. Malkin: Can optimally-fair coin tossing be based on one-way functions?, in: Theory of Cryptography - TCC, 217\u2013239, 2014."},{"issue":"39","key":"4147_CR17","volume":"7","year":"2000","unstructured":"Y. Dodis: Impossibility of black-box reduction from non-adaptively to adaptively secure coin-flipping, Electronic Colloquium on Computational Complexity (ECCC), 7(39), 2000.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"4147_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D P Dubhashi","year":"2009","unstructured":"D. P. Dubhashi and A. Panconesi: Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, 2009."},{"key":"4147_CR19","volume-title":"CoRR","author":"O Etesami","year":"2019","unstructured":"O. Etesami, S. Mahloujifar and M. Mahmoody: Computational concentration of measure: Optimal bounds, reductions, and more, CoRR, arXiv:1907.05401, 2019."},{"key":"4147_CR20","first-page":"142","volume-title":"40th Annual Symposium on Foundations of Computer Science, FOGS","author":"U Feige","year":"1999","unstructured":"U. Feige: Noncryptographic selection protocols, in: 40th Annual Symposium on Foundations of Computer Science, FOGS, 142\u2013153, 1999."},{"key":"4147_CR21","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/978-3-662-47666-6_53","volume-title":"42nd International Colloquium on Automata, Languages and Programming,, ICALP","author":"S Goldwasser","year":"2015","unstructured":"S. Goldwasser, Y. T. Kalai and S. Park: Adaptively secure coin-flipping, revisited, in: 42nd International Colloquium on Automata, Languages and Programming,, ICALP, 663\u2013674, 2015."},{"key":"4147_CR22","first-page":"539","volume-title":"Theory of Cryptography - 16th International Conference, TCC","author":"I Haitner","year":"2018","unstructured":"I. Haitner, N. Makriyannis and E. Omri: On the complexity of fair coin nipping, in: Theory of Cryptography - 16th International Conference, TCC, 539\u2013562, 2018."},{"key":"4147_CR23","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1137\/120887631","volume":"43","author":"I Haitner","year":"2014","unstructured":"I. Haitner and E. Omri: Coin nipping with constant bias implies one-way functions, SIAM J. Comput. 43 (2014), 389\u2013409.","journal-title":"SIAM J. ^Comput."},{"key":"4147_CR24","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1137\/15M1009147","volume":"46","author":"I Haitner","year":"2017","unstructured":"I. Haitner and E. Tsfadia: An almost-optimally fair three-party coin-flipping protocol, SIAM J. Comput. 46 (2017), 479\u2013542.","journal-title":"SIAM J. Comput."},{"key":"4147_CR25","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1109\/SFCS.1989.63483","volume-title":"30th Annual Symposium on Foundations of Computer Science, FOCS","author":"R Impagliazzo","year":"1989","unstructured":"R. Impagliazzo and M. Luby: One-way functions are essential for complexity based cryptography (extended abstract), in: 30th Annual Symposium on Foundations of Computer Science, FOCS, 230\u2013235. IEEE Computer Society, 1989."},{"key":"4147_CR26","first-page":"467","volume-title":"Distributed Computing - 29th International Symposium, DISC","author":"Y T Kalai","year":"2015","unstructured":"Y. T. Kalai and I. Komargodski: Compressing communication in distributed protocols, in: Distributed Computing - 29th International Symposium, DISC, 467\u2013479, 2015."},{"key":"4147_CR27","first-page":"68","volume-title":"29th Annual Symposium on Foundations of Computer Science, FOCS","author":"J Kahn","year":"1988","unstructured":"J. Kahn, G. Kalai and N. Linial: The influence of variables on boolean functions (extended abstract), in: 29th Annual Symposium on Foundations of Computer Science, FOCS, 68\u201380, 1988."},{"key":"4147_CR28","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02125896","volume":"9","author":"D Llchtenstein","year":"1989","unstructured":"D. Llchtenstein, N. Llnial and M. E. Saks: Some extremal problems arising form discrete control processes, Combinatorial 9 (1989), 269\u2013287.","journal-title":"Combinatorial"},{"key":"4147_CR29","first-page":"581","volume-title":"Algorithmic Learning Theory, ALT","author":"S Mahloujifar","year":"2019","unstructured":"S. Mahloujifar and M. Mahmoody: Can adversarially robust learning leverage-computational hardness? in: Algorithmic Learning Theory, ALT, 581\u2013609, 2019."},{"key":"4147_CR30","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s00145-015-9199-z","volume":"29","author":"T Moran","year":"2016","unstructured":"T. Moran, M. Naor and G. Segev: An optimally fair coin toss, J. Cryptology 29 (2016), 491\u2013513.","journal-title":"J. Cryptology"},{"key":"4147_CR31","first-page":"613","volume-title":"51th Annual IEEE Symposium on Foundations of Computer Science, FOCS","author":"H K Maji","year":"2010","unstructured":"H. K. Maji, M. Prabhakaran and A. Sahai: On the computational complexity of coin nipping, in: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS, 613\u2013622. IEEE Computer Society, 2010."},{"key":"4147_CR32","doi-asserted-by":"publisher","first-page":"1645","DOI":"10.1137\/S0097539700376007","volume":"31","author":"A Russell","year":"2002","unstructured":"A. Russell, M. E. Saks and D. Zuckerman: Lower bounds for leader election and collective coin-flipping in the perfect information model, SIAM J. Comput. 31 (2002), 1645\u20131662.","journal-title":"SIAM J. Comput."},{"key":"4147_CR33","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/0402020","volume":"2","author":"M E Saks","year":"1989","unstructured":"M. E. Saks: A robust noncryptographic protocol for collective coin flipping, SIAM J. Discrete Math. 2 (1989), 240\u2013244.","journal-title":"SIAM J. Discrete Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4147-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-020-4147-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4147-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T16:06:01Z","timestamp":1616601961000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-020-4147-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,30]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["4147"],"URL":"https:\/\/doi.org\/10.1007\/s00493-020-4147-4","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,30]]},"assertion":[{"value":"31 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}