0368-4170-01, Fall 2009:
Cryptography and Game Theory
Wednesdays 11-14, Dan David 209.
Instructors: Ran Canetti
and Alon Rosen
To Join the course mailing list, send email to: firstname.lastname@example.org
with the following message body: subscribe 0368-4170-01 Your Name
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:
Background in Game Theory:
Basics: Indisitinguishability, Encryption, Zero Knowledge,
Secure Computation: Definitions, basic constructions
Fairness in secure computation: Definitions, constructions,
Cryptographic 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,
Computational notions of Nash Equilibria
Replacing trusted mediators via cryptographic means
Rational Secure computation: Basic formalisms, Rational secret
sharing (Two-party and multi-party).
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
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.
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
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
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.
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.