skip to main content
10.1145/1146381.1146393acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation

Published: 23 July 2006 Publication History

Abstract

We study k-resilient Nash equilibria, joint strategies where no member of a coalition C of size up to k can do better, even if the whole coalition defects. We show that such k-resilient Nash equilibria exist for secret sharing and multiparty computation, provided that players prefer to get the information than not to get it. Our results hold even if there are only 2 players, so we can do multiparty computation with only two rational agents. We extend our results so that they hold even in the presence of up to t players with "unexpected" utilities. Finally, we show that our techniques can be used to simulate games with mediators by games without mediators.

References

[1]
E. Adar and B. Huberman. Free riding on Gnutella. First Monday, 5(10), 2000.
[2]
R Aumann. Acceptable points in general cooperative n-person games. Contributions to the Theory of Games, Annals of Mathematical Studies, IV:287--324, 1959.
[3]
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proc. 20th ACM Symp. Theory of Computing, pages 1--10, 1988.
[4]
E. Ben-Porath. Cheap talk in games with incomplete information. J. Economic Theory, 108(1):45--71, 2003.
[5]
B. D. Bernheim, B. Peleg, and M. Whinston. Coalition proof Nash equilibrium: Concepts. J. Economic Theory, 42(1):1--12, 1989.
[6]
F. M. Forges. An approach to communication equilibria. Econometrica, 54(6):1375--85, 1986.
[7]
O. Goldreich. Foundations of Cryptography, Vol. 2. Cambridge University Press, 2004.
[8]
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proc. 19th ACM Symp. Theory of Computing, pages 218--229, 1987.
[9]
D. Gordon and J. Katz. Rational secret sharing, revisited. Unpublished manuscript, 2006.
[10]
J. Y. Halpern and V. Teague. Rational secret sharing and multiparty computation: extended abstract. In Proc. 36th ACM Symp. Theory of Computing, pages 623--632, 2004.
[11]
Yuval Heller. A minority-proof cheap-talk protocol. Unpublished manuscript, 2005.
[12]
S. Izmalkov, S. Micali, and M. Lepinski. Rational secure computation and ideal mechanism design. In Proc. 46th IEEE Symp. Foundations of Computer Science, pages 585--595, 2005.
[13]
J. Justesen. On the complexity of decoding Reed-Solomon codes (corresp). IEEE Trans. on Information Theory, 22(2):237--238, 1976.
[14]
L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals problem. ACM Trans. on Programming Languages and Systems, 4(3):382--401, 1982.
[15]
M. Lepinksi, S. Micali, and A. Shelat. Collusion-free protocols. In Proc. 37th ACM Symp. Theory of Computing, pages 543--552, 2005.
[16]
M. Lepinski, S. Micali, C. Peikert, and A. Shelat. Completely fair SFE and coalition-safe cheap talk. In Proc. 23rd ACM Symp. Principles of Distributed Computing, pages 1--10, 2004.
[17]
A. Lysyanskaya and N. Triandopoulos. Rationality and adversarial behavior in multi-party computation. Unpublished manuscript, 2006.
[18]
D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay - secure two-party computation system. In Proc. 13th USENIX Security Symposium, pages 287--302, 2004.
[19]
D. Moreno and J. Wooders. Coalition-proof equilibrium. Games and Economic Behavior, 17(1):80--112, 1996.
[20]
G. Neiger and S. Toueg. Automatically increasing the fault-tolerance of distributed algorithms. Journal of Algorithms, 11(3):374--419, 1990.
[21]
M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, Cambridge, Mass., 1994.
[22]
T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proc. 21st ACM Symp. Theory of Computing, pages 73--85, 1989.
[23]
A. Shamir. How to share a secret. Commun. ACM, 22(11):612--613, 1979.
[24]
Y. Shoham and M. Tennenholtz. Non-cooperative computing: Boolean functions with correctness and exclusivity. Theoretical Computer Science, 343(1--2):97--113, 2005.
[25]
A. Yao. Protocols for secure computation (extended abstract). In Proc. 23rd IEEE Symp. Foundations of Computer Science, pages 160--164, 1982.

Cited By

View all
  • (2024)Making a Nash Equilibrium Resilient to CoalitionsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673552(213-238)Online publication date: 8-Jul-2024
  • (2024)Bounding the communication complexity of fault-tolerant common coin tossingACM Transactions on Computation Theory10.1145/367076916:3(1-10)Online publication date: 8-Aug-2024
  • (2024)Secure Vickrey Auctions with Rational PartiesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670311(4062-4076)Online publication date: 2-Dec-2024
  • Show More Cited By

Index Terms

  1. Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
    July 2006
    230 pages
    ISBN:1595933840
    DOI:10.1145/1146381
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 July 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. distributed computing
    2. game theory
    3. secret sharing
    4. secure multiparty computation

    Qualifiers

    • Article

    Conference

    PODC06

    Acceptance Rates

    Overall Acceptance Rate 740 of 2,477 submissions, 30%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)62
    • Downloads (Last 6 weeks)8
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Making a Nash Equilibrium Resilient to CoalitionsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673552(213-238)Online publication date: 8-Jul-2024
    • (2024)Bounding the communication complexity of fault-tolerant common coin tossingACM Transactions on Computation Theory10.1145/367076916:3(1-10)Online publication date: 8-Aug-2024
    • (2024)Secure Vickrey Auctions with Rational PartiesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670311(4062-4076)Online publication date: 2-Dec-2024
    • (2024)Verifiable Crowd Computing: Coping with Bounded RationalityTheoretical Computer Science10.1016/j.tcs.2024.114631(114631)Online publication date: May-2024
    • (2024)Communication games, sequential equilibrium, and mediatorsJournal of Economic Theory10.1016/j.jet.2024.105890(105890)Online publication date: Aug-2024
    • (2024)Beyond dominance and Nash: Ranking equilibria by critical massGames and Economic Behavior10.1016/j.geb.2024.01.011Online publication date: Feb-2024
    • (2024)Privacy-Preserving Distributed Optimization and LearningReference Module in Materials Science and Materials Engineering10.1016/B978-0-443-14081-5.00125-2Online publication date: 2024
    • (2024)A rational hierarchical (t,n)-threshold quantum secret sharing schemeQuantum Information Processing10.1007/s11128-024-04269-123:2Online publication date: 12-Feb-2024
    • (2024)Viable Nash equilibria: an experimentEconomic Theory10.1007/s00199-024-01585-6Online publication date: 19-Jun-2024
    • (2024)Game-Theoretically Fair Distributed SamplingAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_7(207-239)Online publication date: 16-Aug-2024
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media