6.876J Cryptographic Game Theory (H)

L TR2-3:30, room 24-407
Prof. Silvio Micali, silvio@csail.mit.edu
Prereq.:
3-0-9

Mutually suspicious individuals with different and even conflicting goals often wish or need to cooperate towards a common goal. Can such cooperation succeed? What should such a success mean? Cryptographic Protocols and Game Theory provide different answers to these important questions, have developed different models, and forged different sets of working tools. This course aims at bridging these two approaches in a systematic way, and gain a new understanding of human interactions. The benefit of a unified approach, or at least one cognizant of the conceptualizations and techniques of both sides, is potentially enormous. (So even a modest success would be great!)

We start by reviewing fundamental notions and results of both fields, and then proceed to open a new approach to “champion problems” such as reaching correlated equilibrium and mechanism design. Topics include:

• Zero-knowledge Proofs

• Secure Function Evaluation

• Complete-Information Games and Equilibria

• Incomplete-Information Games and Sequential Reasoning

• Concurrency and Security

• Signaling and Security

• Collusion-free Security

• Correlated Equilibria via Extended Games

• Ideal Mechanism Design

This is an experimental course, and active participation is essential. No prerequisites beyond basic efficient algorithms and Theory of Computation ---though some knowledge of Cryptography (e.g., 6.875) or Game Theory (e.g., 6.972 or 14.122) would be very useful.