Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

A Cryptographic Solution to a Game Theoretic Problem

Yevgeniy Dodis, Shai Halevi, Tal Rabin

Published Jan 1, 2000• 87 citations
Publisher
DOI
10.1007/3-540-44598-6_7

Related papers

Cryptography and Game Theory

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.

Algorithmic Game Theory•Sep 24, 2007•62 citations

Toward a Game Theoretic View of Secure Computation

Gilad Asharov, Ran Canetti, Carmit Hazay

Journal of Cryptology•Aug 13, 2015•6 citations

Cryptography and Game Theory: Designing Protocols for Exchanging Information

Gillat Kol, Moni Naor

Springer eBooks•Feb 25, 2008•180 citations

An application of game theoretic techniques to cryptography

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

DIMACS series in discrete mathematics and theoretical computer science•Oct 25, 1993•31 citations

Towards a Game Theoretic View of Secure Computation

Gilad Asharov, Ran Canetti, Carmit Hazay

Lecture notes in computer science•Jan 1, 2011•84 citations

Optimal Channel Design: A Game Theoretical Analysis

M. H. R. Khouzani, Pasquale Malacaria

This paper studies the problem of optimal channel design. For a given input probability distribution and for hard and soft design constraints, the aim here is to design a (probabilistic) channel whose output leaks minimally from its input. To analyse this problem, general notions of entropy and information leakage are introduced. It can be shown that, for all notions of leakage here defined, the optimal channel design problem can be solved using convex programming with zero duality gap. Subsequently, the optimal channel design problem is studied in a game-theoretical framework: games allow for analysis of optimal strategies of both the defender and the adversary. It is shown that all channel design problems can be studied in this game-theoretical framework, and that the defender's Bayes-Nash equilibrium strategies are equivalent to the solutions of the convex programming problem. Moreover, the adversary's equilibrium strategies correspond to a robust inference problem.

Entropy•Sep 5, 2018•7 citations
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.
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...
This paper studies the problem of optimal channel design. For a given input probability distribution and for hard and soft design constraints, the aim here is to design a (probabilistic) channel whose output leaks minimally from its input. To analyse this problem, general notions of entropy and information leakage are introduced. It can be shown that, for all notions of leakage here defined, the optimal channel design problem can be solved using convex programming with zero duality gap. Subsequently, the optimal channel design problem is studied in a game-theoretical framework: games allow for analysis of optimal strategies of both the defender and the adversary. It is shown that all channel design problems can be studied in this game-theoretical framework, and that the defender's Bayes-Nash equilibrium strategies are equivalent to the solutions of the convex programming problem. Moreover, the adversary's equilibrium strategies correspond to a robust inference problem.