{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T13:09:37Z","timestamp":1765112977958,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031159817"},{"type":"electronic","value":"9783031159824"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15982-4_14","type":"book-chapter","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T04:40:54Z","timestamp":1665463254000},"page":"409-438","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["$$\\log ^*$$-Round Game-Theoretically-Fair Leader Election"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1647-2112","authenticated-orcid":false,"given":"Ilan","family":"Komargodski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3208-4531","authenticated-orcid":false,"given":"Shin\u2019ichiro","family":"Matsuo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2756-8750","authenticated-orcid":false,"given":"Ke","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,12]]},"reference":[{"key":"14_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-48000-6_21","volume-title":"Advances in Cryptology - ASIACRYPT\u201999","author":"M Abe","year":"1999","unstructured":"Abe, M.: Mix-networks on permutation networks. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 258\u2013273. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-3-540-48000-6_21"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-642-20465-4_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"G Asharov","year":"2011","unstructured":"Asharov, G., Canetti, R., Hazay, C.: Towards a game theoretic view of secure computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 426\u2013445. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20465-4_24"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: PODC (2006)","DOI":"10.1145\/1146381.1146393"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: S &P (2014)","DOI":"10.1109\/SP.2014.35"},{"issue":"1","key":"14_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s00145-010-9064-z","volume":"24","author":"G Asharov","year":"2011","unstructured":"Asharov, G., Lindell, Y.: Utility dependence in correct and fair rational secret sharing. J. Cryptol. 24(1), 157\u2013202 (2011)","journal-title":"J. Cryptol."},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-662-53641-4_13","volume-title":"Theory of Cryptography","author":"B Alon","year":"2016","unstructured":"Alon, B., Omri, E.: Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 307\u2013335. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53641-4_13"},{"key":"14_CR7","volume-title":"The Probabilistic Method","author":"N Alon","year":"2016","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, Hoboken (2016)"},{"issue":"1","key":"14_CR8","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0304-4068(74)90037-8","volume":"1","author":"RJ Aumann","year":"1974","unstructured":"Aumann, R.J.: Subjectivity and correlation in randomized strategies. J. Math. Econ. 1(1), 67\u201396 (1974)","journal-title":"J. Math. Econ."},{"key":"14_CR9","unstructured":"Beimel, A., Groce, A., Katz, J., Orlov, I.: Fair computation with rational players. Cryptology ePrint Archive (2011)"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-3-662-44381-1_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"I Bentov","year":"2014","unstructured":"Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 421\u2013439. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44381-1_24"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Blum, M.: Coin flipping by telephone a protocol for solving impossible problems. SIGACT News (1983)","DOI":"10.1145\/1008908.1008911"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1007\/978-3-642-14623-7_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"A Beimel","year":"2010","unstructured":"Beimel, A., Omri, E., Orlov, I.: Protocols for multiparty coin toss with dishonest majority. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 538\u2013557. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14623-7_29"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-84245-1_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"K-M Chung","year":"2021","unstructured":"Chung, K.-M., Chan, T.-H.H., Wen, T., Shi, E.: Game-theoretic fairness meets multi-party protocols: the case of leader election. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 3\u201332. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84245-1_1"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Corrigan-Gibbs, H., Fordm, B.: Dissent: accountable anonymous group messaging. In: CCS (2010)","DOI":"10.1145\/1866307.1866346"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-030-03807-6_21","volume-title":"Theory of Cryptography","author":"K-M Chung","year":"2018","unstructured":"Chung, K.-M., Guo, Y., Lin, W.-K., Pass, R., Shi, E.: Game theoretic notions of fairness in multi-party coin toss. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11239, pp. 563\u2013596. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03807-6_21"},{"issue":"2","key":"14_CR16","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/358549.358563","volume":"24","author":"DL Chaum","year":"1981","unstructured":"Chaum, D.L.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24(2), 84\u201390 (1981)","journal-title":"Commun. ACM"},{"issue":"1","key":"14_CR17","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF00206326","volume":"1","author":"D Chaum","year":"1988","unstructured":"Chaum, D.: The dining cryptographers problem: unconditional sender and recipient untraceability. J. Cryptol. 1(1), 65\u201375 (1988)","journal-title":"J. Cryptol."},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: STOC (1986)","DOI":"10.1145\/12130.12168"},{"key":"14_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/3-540-44598-6_7","volume-title":"Advances in Cryptology \u2014 CRYPTO 2000","author":"Y Dodis","year":"2000","unstructured":"Dodis, Y., Halevi, S., Rabin, T.: A cryptographic solution to a game theoretic problem. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 112\u2013130. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44598-6_7"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Dingledine, R., Mathewson, N., Syverson, P.: Tor: the second-generation onion router. Technical report (2004)","DOI":"10.21236\/ADA465464"},{"key":"14_CR21","unstructured":"Dodis, Y.: Fault-tolerant leader election and collective coin-flipping in the full information model (2006)"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Rabin, T., et al.: Cryptography and game theory. Algorithmic Game Theory 181\u2013207 (2007)","DOI":"10.1017\/CBO9780511800481.010"},{"key":"14_CR23","unstructured":"Feige, U.: Noncryptographic selection protocols. In: FOCS (1999)"},{"key":"14_CR24","unstructured":"Gelashvili, R., Goren, G., Spiegelman, A.: Short paper: on game-theoretically-fair leader election"},{"key":"14_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-642-29011-4_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"A Groce","year":"2012","unstructured":"Groce, A., Katz, J.: Fair computation with rational players. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 81\u201398. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_7"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Garay, J., Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Rational protocol design: cryptography against incentive-driven adversaries. In: FOCS (2013)","DOI":"10.1109\/FOCS.2013.75"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Garay, J., Katz, J., Tackmann, B., Zikas, V.: How fair is your protocol? A utility-based approach to protocol optimality. In: PODC (2015)","DOI":"10.1145\/2767386.2767431"},{"key":"14_CR28","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game, or a completeness theorem for protocols with honest majority. In: STOC (2019)"},{"key":"14_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/978-3-662-48653-5_33","volume-title":"Distributed Computing","author":"J Garay","year":"2015","unstructured":"Garay, J., Tackmann, B., Zikas, V.: Fair distributed computation of reactive functions. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 497\u2013512. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48653-5_33"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Halpern, J., Teague, V.: Rational secret sharing and multiparty computation. In: STOC (2004)","DOI":"10.1145\/1007352.1007447"},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Haitner, I., Tsfadia, E.: An almost-optimally fair three-party coin-flipping protocol. In: STOC (2014)","DOI":"10.1145\/2591796.2591842"},{"key":"14_CR32","unstructured":"Izmalkov, S., Micali, S., Lepinski, M.: Rational secure computation and ideal mechanism design. In: FOCS (2005)"},{"key":"14_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-540-78524-8_15","volume-title":"Theory of Cryptography","author":"J Katz","year":"2008","unstructured":"Katz, J.: Bridging game theory and cryptography: recent results and future directions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 251\u2013272. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_15"},{"key":"14_CR34","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Matsuo, S., Shi, E., Wu, K.: log*-round game-theoretically-fair leader election. Cryptology ePrint Archive, Paper 2022\/791 (2022). https:\/\/eprint.iacr.org\/2022\/791","DOI":"10.1007\/978-3-031-15982-4_14"},{"key":"14_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-540-78524-8_18","volume-title":"Theory of Cryptography","author":"G Kol","year":"2008","unstructured":"Kol, G., Naor, M.: Cryptography and game theory: designing protocols for exchanging information. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 320\u2013339. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_18"},{"key":"14_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/978-3-540-78524-8_31","volume-title":"Theory of Cryptography","author":"H Lin","year":"2008","unstructured":"Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent non-malleable commitments from any one-way function. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 571\u2013588. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_31"},{"key":"14_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-00457-5_1","volume-title":"Theory of Cryptography","author":"T Moran","year":"2009","unstructured":"Moran, T., Naor, M., Segev, G.: An optimally fair coin toss. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 1\u201318. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00457-5_1"},{"key":"14_CR38","doi-asserted-by":"crossref","unstructured":"Nash, J.: Non-cooperative games. Ann. Math. 286\u2013295 (1951)","DOI":"10.2307\/1969529"},{"key":"14_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-642-00457-5_3","volume-title":"Theory of Cryptography","author":"SJ Ong","year":"2009","unstructured":"Ong, S.J., Parkes, D.C., Rosen, A., Vadhan, S.: Fairness with an honest minority and a rational majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 36\u201353. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00457-5_3"},{"key":"14_CR40","doi-asserted-by":"crossref","unstructured":"Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: STOC (2004)","DOI":"10.1145\/1007352.1007393"},{"key":"14_CR41","doi-asserted-by":"crossref","unstructured":"Pass, R., Shi, E.: FruitChains: a fair blockchain. In: PODC (2017)","DOI":"10.1145\/3087801.3087809"},{"issue":"6","key":"14_CR42","doi-asserted-by":"publisher","first-page":"1645","DOI":"10.1137\/S0097539700376007","volume":"31","author":"A Russell","year":"2002","unstructured":"Russell, A., Saks, M., Zuckerman, D.: Lower bounds for leader election and collective coin-flipping in the perfect information model. SIAM J. Comput. 31(6), 1645\u20131662 (2002)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"14_CR43","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1006\/jcss.2001.1776","volume":"63","author":"A Russell","year":"2001","unstructured":"Russell, A., Zuckerman, D.: Perfect information leader election in log* n+ o (1) rounds. J. Comput. Syst. Sci. 63(4), 612\u2013626 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"14_CR44","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/293411.298019","volume":"42","author":"P Syverson","year":"1999","unstructured":"Syverson, P., Goldschlag, D., Reed, M.: Onion routing for anonymous and private internet connections. Commun. ACM 42(2), 5 (1999)","journal-title":"Commun. ACM"},{"issue":"11","key":"14_CR45","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. ACM 22(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"14_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-031-06944-4_5","volume-title":"Advances in Cryptology","author":"K Wu","year":"2022","unstructured":"Wu, K., Asharov, G., Shi, E.: A complete characterization of game-theoretically fair, multi-party coin toss. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13275, pp. 120\u2013149. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-06944-4_5"},{"key":"14_CR47","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Protocols for secure computations. In: FOCS (1982)","DOI":"10.1109\/SFCS.1982.38"},{"key":"14_CR48","unstructured":"Zhuang, L., Zhou, F., Zhao, B.Y., Rowstron, A.: Cashmere: resilient anonymous routing. In: NSDI (2005)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15982-4_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:06:50Z","timestamp":1760134010000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15982-4_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159817","9783031159824"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15982-4_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"12 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"42","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}