Cryptography and Game Theory: Designing Protocols for Exchanging Information

Oana Ciobotaru

Rational cryptography has recently emerged as a very promising field of research by combining notions and techniques from cryptography and game theory, because it offers an alternative to the rather inexible traditional cryptographic model. In contrast to the classical view of cryptography where protocol participants are considered either honest or arbitrarily malicious, rational cryptography models participants as rational players that try to maximize their benefit and thus deviate from the protocol only if they gain an advantage by doing so. The main research goals for rational cryptography are the design of more ecient protocols when players adhere to a rational model, the design and implementation of automated proofs for rational security notions and the study of the intrinsic connections between game theoretic and cryptographic notions. In this thesis, we address all these issues. First we present the mathematical model and the design for a new rational file sharing protocol which we call RatFish. Next, we develop a general method for automated verification for rational cryptographic protocols and we show how to apply our technique in order to automatically derive the rational security property for RatFish. Finally, we study the intrinsic connections between game theory and cryptography by defining a new game theoretic notion, which we call game universal implementation, and by showing its equivalence with the notion of weak stand-alone security.

Yevgeniy Dodis, Shai Halevi, Tal Rabin

Gillat Kol, Moni Naor

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.

Samuel M. Scott

Michael J. Fischer, Rebecca N. Wright

This paper provides an application of game theoretic techniques to the analysis of a class of multiparty cryptographic protocols for secret bit exchange. 1 Introduction A cryptographic protocol is often thought of as a game between the honest participants in the protocol and a malicious adversary who tries to corrupt the protocol. In this paper, we consider a simple combinatorial game that arises in the analysis of the class of multiparty "key set" secret bit exchange protocols introduced in [FW92b]. We find an optimal strategy for the combinatorial game and show how this leads to a key set protocol that is optimal from among the class of all key set protocols. While key set protocols are too limited to be of much practical interest, this result is nevertheless interesting as an illustration of the close connection between protocols and games and the use of nontrivial game theoretic techniques in the analysis of protocols. The combinatorial game is a simple counting game a little l...

Arto K. Salomaa