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: Abraham, D. Dolev, R. Gonen, and J. Halpern.Distributed Computing Meets Game Theory: Robust Mechanisms forRational Secret Sharing and Multiparty Computation. InProceedings of the 25th ACM Symposium on Principles of DistributedComputing (PODC), pages 53--62, 2006.
• 2: Boneh and M. Naor. Timed commitments, Advancesin Cryptology -- CRYPTO 2000, Springer LNCS 1880,pages 236--254, 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: Halpern and V. Teague. Rational SecretSharing and Multiparty Computation. In Proceedings of the36th Annual ACM Symposium on Theory of Computing (STOC), pages623--632, 2004.
• 6: Izmalkov, S. Micali, and M. Lepinski. RationalSecure Computation and Ideal Melearnchanism Design. InProceedings of the 46th IEEE Symposium of Foundations of ComputerScience (FOCS), pages 585--595, 2005.
• 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: Lepinski, S. Micali, C. Peikert, and A. Shelat.Completely Fair SFE and Coalition--Safe Cheap Talk. InProceedings of the 23rd ACM Symposium on Principles of DistributedComputing (PODC), pages 1--10, 2004.
• 9: Lepinski, S. Micali, and A. Shelat. Collusion--FreeProtocols. In Proceedings of the 37th Annual ACM Symposiumon Theory of Computing (STOC), pages 543--552, 2005.
• 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: Rabin and M. Ben--Or. Verifiable Secret Sharingand Multiparty Protocols with Honest Majority. InProceedings of the 21th Annual ACM Symposium on Theory ofComputing (STOC), pages 73--85, 1989.
• 14: Shamir. How to share a secret. Communicationsof the ACM, volume 22, pages 612--613, 1979.
• 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