A Cryptographic Solution to a Game Theoretic Problem

Gillat Kol, Moni Naor

Yevgeniy Dodis, Shai Halevi, Tal Rabin

Abstract. In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of “self-enforcing ” strategies making each player’s strategy an optimal response to the other player’s strategy. It is known that for many games the expected equilibrium payoffs can be much higher when a trusted third party (a “mediator”) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism that eliminates the need for the mediator yet allows the players to maintain the high payoffs offered by mediator-assisted strategies. We answer this question affirmatively provided the players are computationally bounded and can have free communication (so-called “cheap talk”) prior to playing the game. The main building block of our solution is an efficient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. Both Alice and Bob know a list of pairs (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games. 1

Gilad Asharov, Ran Canetti, Carmit Hazay

Yevgeniy Dodis, Tal Rabin

The Cryptographic and Game Theory worlds seem to have an intersection in that they both deal with an interaction between mutually distrustful parties which has some end result. In the cryptographic setting the multiparty interaction takes the shape of a set of parties communicating for the purpose of evaluating a function on their inputs, where each party receives at the end some output of the computation. In the game theoretic setting, parties interact in a game that guarantees some payoff for the participants according to the joint actions of all the parties, while the parties wish to maximize their own payoff. In the past few years the relationship between these two areas has been investigated with the hope of having cross fertilization and synergy. In this chapter we describe the two areas, the similarities and differences, and some of the new results stemming from their interaction. The first and second section will describe the cryptographic and the game theory settings (respectively). In the third section we contrast the two settings, and in the last sections we detail some of the existing results. Cryptographic Notions and Settings Cryptography is a vast subject requiring its own book. Therefore, in the following we will give only a high-level overview of the problem of Multi-Party Computation (MPC), ignoring most of the lower-level details and concentrating only on aspects relevant to Game Theory.

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...

Gilad Asharov, Ran Canetti, Carmit Hazay