Games for exchanging information

Gillat Kol, Moni Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

82 Scopus citations

Abstract

We consider the rational versions of two of the classical problems in foundations of cryptography: secret sharing and multiparty computation, suggested by Halpern and Teague (STOC 2004). Our goal is to design games and fair strategies that encourage rational participants to exchange information about their inputs for their mutual benefit, when the only mean of communication is a broadcast channel. We show that protocols for the above information exchanging tasks, where players' values come from a bounded domain, cannot satisfy some of the most desirable properties. In contrast, we provide a rational secret sharing scheme with simultaneous broadcast channel in which shares are taken from an unbounded domain, but have finite (and poly-nomial sized) expectation. Previous schemes (mostly cryptographic) have required computational assumptions, making them inexact and susceptible to backward induction, or used stronger communication channels. Our scheme is non-cryptographic, immune to backward induction, and satisfies a stronger rationality concept (strict Nash equilibrium). We show that our solution can also be used to construct an ε-Nash equilibrium secret sharing scheme for the case of a non-simultaneous broadcast channel.

Original languageEnglish (US)
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the 2008 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery (ACM)
Pages423-432
Number of pages10
ISBN (Print)9781605580470
DOIs
StatePublished - Jan 1 2008
Externally publishedYes
Event40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada
Duration: May 17 2008May 20 2008

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other40th Annual ACM Symposium on Theory of Computing, STOC 2008
CountryCanada
CityVictoria, BC
Period5/17/085/20/08

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Backward induction
  • Computation
  • Cryptography
  • Game theory
  • Multiparty
  • Nash equilibrium
  • Secret sharing

Fingerprint Dive into the research topics of 'Games for exchanging information'. Together they form a unique fingerprint.

  • Cite this

    Kol, G., & Naor, M. (2008). Games for exchanging information. In STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing (pp. 423-432). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery (ACM). https://doi.org/10.1145/1374376.1374437