Games for exchanging information

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 polynomial 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.

REFERENCES

• 1: Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146393]
• 2: Dan Boneh , Moni Naor, Timed Commitments, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.236-254, August 20-24, 2000
• 3: Garay and M. Jakobsson. Timed Releaseof Standard Digital Signatures, In Proceedings of FinancialCryptography, LNCS 2357, pages 168--182, Springer, 2002.
• 4: D. Gordon and J. Katz. Rational Secret Sharing,Revisited. Security and Cryptography for Networks (SCN),pages 229--241, 2006.
• 5: Joseph Halpern , Vanessa Teague, Rational secret sharing and multiparty computation: extended abstract, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007447]
• 6: Sergei Izmalkov , Silvio Micali , Matt Lepinski, Rational Secure Computation and Ideal Mechanism Design, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.585-595, October 23-25, 2005 [doi>10.1109/SFCS.2005.64]
• 7: Kol and M. Naor. Cryptography and Game Theory:Designing Protocols for Exchanging Information. In theProceedings of the 5th Theory of Cryptography Conference (TCC),pages 317--336, 2008.
• 8: Matt Lepinski , Silvio Micali , Chris Peikert , Abhi Shelat, Completely fair SFE and coalition-safe cheap talk, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011769]
• 9: Matt Lepinksi , Silvio Micali , abhi shelat, Collusion-free protocols, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060671]
• 10: Lysyanskaya and N. Triandopoulos.Rationality and Adversarial Behavior in Multi--Party Computation.Advances in Cryptology -- CRYPTO 2006, pages 180--197, 2006.
• 11: Osborne and A. Rubinstein. A Course in GameTheory, MIT Press, 1994.
• 12: Pinkas. Fair Secure Two--Party Computation. Advancesin Cryptology -- Eurocrypt 2003, pages 87--105, 2003.
• 13: T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
• 14: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 15: Wegman and L. Carter. New hash functionsand their use in authentication and set equality. Journal ofComputer and System Sciences, volume 22, pages 265--279, 1981.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Theory

Keywords:
backward induction, cryptography, game theory, multiparty computation, nash equilibrium, secret sharing