0368417001, Fall 2009:
Cryptography and Game Theory
Wednesdays 1114, 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 0368417001 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 openended, concerning itself with understanding "natural"
algorithmic behaviors of parties with welldefined 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:

Zerosum games, the minmax theorem.

Normal form games: Nash equilibrium, correlated equilibrium,
dominated strategies, approximate Nash equilibria.

Extensive form games: Subgame perfection, imperfect/incomplete information,
Bayesian/sequential/tremblinghand equilibria.
Cryptographic Game Theory:

Computational notions of Nash Equilibria

Replacing trusted mediators via cryptographic means

Rational Secure computation: Basic formalisms, Rational secret
sharing (Twoparty and multiparty).
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.
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 0262650401. 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, SpringerVerlag (LNCS 4948), pages
251272, 2008.

Y. Dodis, S. Halevi and T. Rabin. A Cryptographic Solution to a
Game Theoretic Problem. CRYPTO'00. SpringerVerlag (LNCS 1880),
pages 112130, 2000.

S. Izmalkov, S. Micali and M.Lepinski. Rational Secure Computation
and Ideal Mechanism Design. 46th FOCS, pages 585595, 2005.

S. Izmalkov, M. Lepinski and S. Micali. Verifiably Secure Devices.
5th TCC, SpringerVerlag (LNCS 4948), pages 273301, 2008.

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

S.D. Gordon and J. Katz. Rational Secret Sharing, Revisited.
Security and Cryptography for Networks (SCN), SpringerVerlag
(LNCS 4116), pages 229241, 2006.

A. Lysyanskaya and N. Triandopoulos. Rationality and Adversarial
Behavior in Multiparty Computation. CRYPTO'06, SpringerVerlag
(LNCS 4117), pages 180197, 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 423432, 2008.

G. Kol and M. Naor. Cryptography and Game Theory: Designing
Protocols for Exchanging Information. 5th TCC, SpringerVerlag (LNCS
4948), pages 320339, 2008.

S. J. Ong, D. C. Parkes, A. Rosen and S. P.Vadhan. Fairness with an
Honest Minority and a Rational Majority. 6th TCC, SpringerVerlag
(LNCS 5444), pages 3653, 2009.
