Paper 2021/1317

m-Stability: Threshold Security Meets Transferable Utility

Osman Biçer, Burcu Yıldız, and Alptekin Küpçü


Use of game theory and mechanism design in cloud security is a well-studied topic. When applicable, it has the advantages of being efficient and simple compared to cryptography alone. Most analyses consider two-party settings, or multi-party settings where coalitions are not allowed. However, many cloud security problems that we face are in the multi-party setting and the involved parties can almost freely collaborate with each other. To formalize the study of disincentivizing coalitions from deviating strategies, a well-known definition named k-resiliency has been proposed by Abraham et al. (ACM PODC '06). Since its proposal, k-resiliency and related definitions are used extensively for mechanism design. However, in this work we observe the shortcoming of k-resiliency. That is, although this definition is secure, it is too strict to use for many cases and rule out secure mechanisms as insecure. To overcome this issue, we propose a new definition named l-repellence against the presence of a single coalition to replace k-resiliency. Our definition incorporates transferable utility in game theory as it is realistic in many distributed and multi-party computing settings. We also propose m-stability definition against the presence of multiple coalitions, which is inspired by threshold security in cryptography. We then show the advantages of our novel definitions on three mechanisms, none of which were previously analyzed against coalitions: incentivized cloud computation, forwarding data packages in ad hoc networks, and connectivity in ad hoc networks. Regarding the former, our concepts improve the proposal by Küpçü (IEEE TDSC '17), by ensuring a coalition-proof mechanism.

Available format(s)
Publication info
threshold securitycooperative game theoryoutsourced computingad hoc net-works
Contact author(s)
obicer17 @ ku edu tr
2021-09-30: last of 4 revisions
2021-09-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Osman Biçer and Burcu Yıldız and Alptekin Küpçü},
      title = {m-Stability: Threshold Security Meets Transferable Utility},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1317},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.