Abstract
Rational multiparty computation (rational MPC) provides a framework for analyzing MPC protocols through the lens of game theory. One way to judge whether an MPC protocol is rational is through weak domination: Rational players would not adhere to an MPC protocol if deviating never decreases their utility, but sometimes increases it.
Secret reconstruction protocols are of particular importance in this setting because they represent the last phase of most (rational) MPC protocols. We show that most secret reconstruction protocols from the literature are not, in fact, stable with respect to weak domination. Furthermore, we formally prove that (under certain assumptions) it is impossible to design a secret reconstruction protocol which is a Nash equilibrium but not weakly dominated if (1) shares are authenticated or (2) half of all players may form a coalition.
This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Centre “On-The-Fly Computing“ under the project number 160364472 – SFB 901/3.
J. Bobolz—Work done while at Paderborn University.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abraham, I., Dolev, D., Gonen, R., Halpern, J.Y.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: Proceedings of the 25th Annual Symposium on Principles of Distributed Computing, PODC, pp. 53–62. ACM (2006)
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–445. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_24
Asharov, G., Lindell, Y.: Utility dependence in correct and fair rational secret sharing. J. Cryptol. 24(1), 157–202 (2011)
Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., et al. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11–46. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20901-7_2
Blömer, J., Bobolz, J., Bröcher, H.: On the impossibility of surviving (iterated) deletion of weakly dominated strategies in rational MPC. Cryptology ePrint Archive, Paper 2022/1762 (2022)
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–32. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_1
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–596. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03807-6_21
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–130. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_7
Dodis, Y., Rabin, T.: Cryptography and game theory. In: Algorithmic Game Theory, pp. 181–207 (2007)
Fuchsbauer, G., Katz, J., Naccache, D.: Efficient rational secret sharing in standard communication networks. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 419–436. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_25
Goldreich, O., Micali, S., Wigderson, A.: 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, pp. 218–229. ACM (1987)
Gordon, S.D., Katz, J.: Rational secret sharing, revisited. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 229–241. Springer, Heidelberg (2006). https://doi.org/10.1007/11832072_16
Groce, A., Katz, J.: Fair computation with rational players. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 81–98. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_7
Halpern, J.Y., Teague, V.: Rational secret sharing and multiparty computation: extended abstract. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 623–632. ACM (2004)
Hillas, J., Samet, D.: Dominance rationality: a unified approach. Games Econ. Behav. 119, 189–196 (2020)
Hubáček, P., Nielsen, J.B., Rosen, A.: Limits on the power of cryptographic cheap talk. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 277–297. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_16
Katz, J.: Bridging game theory and cryptography: recent results and future directions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 251–272. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_15
Kol, G., Naor, M.: Cryptography and game theory: designing protocols for exchanging information. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 320–339. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_18
Kol, G., Naor, M.: Games for exchanging information. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 423–432 (2008)
Lysyanskaya, A., Triandopoulos, N.: Rationality and adversarial behavior in multi-party computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 180–197. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_11
Manshaei, M.H., Zhu, Q., Alpcan, T., Bacşar, T., Hubaux, J.P.: Game theory meets network security and privacy. ACM Comput. Surv. (CSUR) 45(3), 1–39 (2013)
Rabin, T.: Robust sharing of secrets when the dealer is honest or cheating. J. ACM 41(6), 1089–1109 (1994)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 73–85. ACM (1989)
Samuelson, L.: Dominated strategies and common knowledge. Games Econ. Behav. 4(2), 284–313 (1992)
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Stahl, D.O.: Lexicographic rationalizability and iterated admissibility. Econ. Lett. 47(2), 155–159 (1995)
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–149. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06944-4_5
Acknowledgements
We would like to thank the anonymous reviewers for their valuable feedback and constructive comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Blömer, J., Bobolz, J., Bröcher, H. (2023). On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational MPC. In: Rothblum, G., Wee, H. (eds) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol 14369. Springer, Cham. https://doi.org/10.1007/978-3-031-48615-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-48615-9_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-48614-2
Online ISBN: 978-3-031-48615-9
eBook Packages: Computer ScienceComputer Science (R0)