0368-4170-01, Fall 2009:
Cryptography and Game Theory


Wednesdays 11-14, Dan David 209.

Instructors: Ran Canetti and Alon Rosen



Scribe Notes
Problem Sets

To Join the course mailing list, send email to: listserv@listserv.tau.ac.il
with the following message body: subscribe 0368-4170-01 Your Name


Syllabus

Both game theory and the discipline of cryptographic protocols are concerned with designing and analyzing algorithmic mechanisms for collaborative interactions among parties with conflicting interests. However, the two disciplines developed very different sets of goals and formalisms. Cryptography focuses on designing algorithms that allow those who follow them to interact in a way that guarantees some basic concrete properties, such as secrecy, correctness or fairness, in face of arbitrary malicious behavior. Game theory is more open-ended, concerning itself with understanding "natural" algorithmic behaviors of parties with well-defined goals in a given situation, and on designing rules of interaction that will lead to behaviors with desirable properties.

In spite of these differences, some very fruitful cross fertilization between the two disciplines has recently taken place. Ideas from both disciplines have been combined to obtain old goals, to draw new ones, and to gain better overall understanding of the nature of collaborative interaction with conflicting interests. Still, much remains to be explored.

This class aims to prepare and motivate graduate students to do research in this area. We will cover some essential background in cryptography and game theory, and then present some of the recent works that combine the two disciplines. More specifically, the plan is to cover the following topics:

Background in Cryptography:

  • Basics: Indisitinguishability, Encryption, Zero Knowledge,
  • Secure Computation: Definitions, basic constructions
  • Fairness in secure computation: Definitions, constructions, impossibility results.
Background in Game Theory:

  • Zero-sum games, the min-max theorem.
  • Normal form games: Nash equilibrium, correlated equilibrium, dominated strategies, approximate Nash equilibria.
  • Extensive form games: Subgame perfection, imperfect/incomplete information, Bayesian/sequential/trembling-hand equilibria.
Cryptographic Game Theory:

  • Computational notions of Nash Equilibria
  • Replacing trusted mediators via cryptographic means
  • Rational Secure computation: Basic formalisms, Rational secret sharing (Two-party and multi-party).

Prerequisites

The most important prerequisite for the class is mathematical maturity, namely the ability to understand new mathematical concepts and complete details on your own. Some knowledge in foundations of cryptography will be very helpful (although a brief review will be given, pending the knowledge of the audience). No prior knowledge in game theory is needed. While the class is primarily aimed at graduate students, senior year undergraduates may be admitted: Please contact the instructors.


Course Requirements

The main requirement in the course will be to prepare high quality class notes (that will be be posted online). There may also be homework and final exam, pending progress of the course.


Bibliography

Reading material in cryptography:


Reading material in game theory:

  • M. J. Osborne and A. Rubinstein. A course in game theory. (MIT Press, 1994), ISBN 0-262-65040-1. The book is also available here.

  • D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.

Reading material in cryptographic game theory:

  • J. Katz. Bridging Game Theory and Cryptography: Recent Results and Future Directions. 5th TCC, Springer-Verlag (LNCS 4948), pages 251--272, 2008.

  • Y. Dodis, S. Halevi and T. Rabin. A Cryptographic Solution to a Game Theoretic Problem. CRYPTO'00. Springer-Verlag (LNCS 1880), pages 112--130, 2000.

  • S. Izmalkov, S. Micali and M.Lepinski. Rational Secure Computation and Ideal Mechanism Design. 46th FOCS, pages 585--595, 2005.

  • S. Izmalkov, M. Lepinski and S. Micali. Verifiably Secure Devices. 5th TCC, Springer-Verlag (LNCS 4948), pages 273--301, 2008.

  • J. Halpern and V. Teague. Efficient Rational Secret Sharing in Standard Communication Networks. 36th STOC, pages 623--632, 2004.

  • S.D. Gordon and J. Katz. Rational Secret Sharing, Revisited. Security and Cryptography for Networks (SCN), Springer-Verlag (LNCS 4116), pages 229--241, 2006.

  • A. Lysyanskaya and N. Triandopoulos. Rationality and Adversarial Behavior in Multi-party Computation. CRYPTO'06, Springer-Verlag (LNCS 4117), pages 180--197, 2006.

  • G. Asharov and Y. Lindell. Utility Dependence in Correct and Fair Rational Secret Sharing. CRYPTO'09.

  • J. Halpern and R. Pass. Game Theory with Costly Computation. Manuscript, 2008.

  • G. Kol and M. Naor. Games for exchanging information. 40th STOC, pages 423-432, 2008.

  • G. Kol and M. Naor. Cryptography and Game Theory: Designing Protocols for Exchanging Information. 5th TCC, Springer-Verlag (LNCS 4948), pages 320--339, 2008.

  • S. J. Ong, D. C. Parkes, A. Rosen and S. P.Vadhan. Fairness with an Honest Minority and a Rational Majority. 6th TCC, Springer-Verlag (LNCS 5444), pages 36--53, 2009.


Scribe Notes



Problem Sets