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

Algorithmic Game Theory

Cryptography and Game Theory

Yevgeniy Dodis, Tal Rabin

Published Sep 24, 2007• 62 citations
Publisher

Abstract

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.

DOI
10.1017/cbo9780511800481.010

Related papers

Rational Multiparty Computation

John Ross Wallrabenstein

The field of rational cryptography considers the design of cryptographic protocols in the presence of rational agents seeking to maximize local utility functions. This departs from the standard secure multiparty computation setting, where players are assumed to be either honest or malicious. We detail the construction of both a two-party and a multiparty game theoretic framework for constructing rational cryptographic protocols. Our framework specifies the utility function assumptions necessary to realize the privacy, correctness, and fairness guarantees for protocols. We demonstrate that our framework correctly models cryptographic protocols, such as rational secret sharing, where existing work considers equilibrium concepts that yield unreasonable equilibria. Similarly, we demonstrate that cryptography may be applied to the game theoretic domain, constructing an auction market not realizable in the original formulation. Additionally, we demonstrate that modeling players as rational agents allows us to design a protocol that destabilizes coalitions. Thus, we establish a mutual benefit from combining the two fields, while demonstrating the applicability of our framework to real-world market environments. We also give an application of game theory to adversarial interactions where cryptography is not necessary. Specifically, we consider adversarial machine learning, where the adversary is rational and reacts to the presence of a data miner. We give a general extension to classification algorithms that returns greater expected utility for the data miner than existing classification methods.

•Jan 1, 2014•1 citation

General Cryptographic Protocols

Oded Goldreich

The design of secure protocols that implement arbitrarily desired functionalities is a major part of modern cryptography. Taking the opposite perspective, the design of any cryptographic scheme may be viewed as the design of a secure protocol for implementing a suitable functionality. Still, we believe that it makes sense to differentiate between basic cryptographic primitives (which involve little interaction) like encryption and signature schemes, on the one hand, and general cryptographic protocols, on the other hand. In this chapter we consider general results concerning secure multi –party computations, where the two –party case is an important special case. In a nutshell, these results assert that one can construct protocols for securely computing any desirable multi–party functionality (see the following terminology). Indeed, what is striking about these results is their generality, and we believe that the wonder is not diminished by the (various alternative) conditions under which these results hold. Our focus on the general study of secure multi–party computation (rather than on protocols for solving specific problems) is natural in the context of the theoretical treatment of the subject matter. We wish to highlight the importance of this general study to practice. Firstly, this study clarifies fundamental issues regarding security in a multi–party environment. Secondly, it draws the lines between what is possible in principle and what is not. Thirdly, it develops general techniques for designing secure protocols. And last, sometimes it may even yield schemes (or modules) that may be incorporated in practical systems.

Cambridge University Press eBooks•May 10, 2004•69 citations

Is multiparty computation any good in practice?

Claudio Orlandi

The aim of this paper is to present some of the recent progress in efficient secure multiparty computation (MPC). In MPC we have a set of parties owning a set of private inputs. The par ties want to compute a function of their inputs, but they do not trust each other, therefore they need a cryptographic protocol to perform the computation in a way that 1) the output is correct and 2) cheating parties will not be able to learn any information about the honest parties inputs. Even though this problem has been formulated and essentially solved almost 30 years ago, practical solutions that can be relevant for real-world applications have been discovered only in the last few years. We will present some of these advances, trying to explain to a non-specialized audience the significance of the several existing security notions.

IEEE International Conference on Acoustics Speech and Signal Processing•May 1, 2011•49 citations

On secret sharing-based classical and quantum multi-party computation

J.G. Hölting

Secure multi-party computation (MPC) is a cryptographic primitive that lets a num- ber N of mutually distrustful parties compute a function f (x1, . . . , xN ) on their private inputs xi such that at the end of the MPC protocol, each honest party obtains the func- tion’s correct output and no adversary controlling a certain subset of parties learns any- thing about the honest parties’ inputs beyond what can be inferred from the function’s output value. In 2002, [Smi01] and [CGS02] introduced the notion of multi-party quan- tum computation (MPQC) in which arbitrary quantum circuits can be evaluated in a distributed manner, secure against a quantum adversary. Few protocols for MPQC are known. We present a fundamental study of the building blocks of MPC and MPQC in the information-theoretic setting with a focus on protocols built on top of (quantum) se- cret sharing schemes. In particular, we point out structural similarities and differences and compile an extensive list of theoretical feasibility results for the maximum number of corrupted parties within classical and quantum secret sharing and MPC protocols.

•Jan 1, 2020•0 citations

Cryptographic protocol design

Sven Laur

In this work, we investigate the security of interactive computations. The main emphasis is on the mathematical methodology that is needed to formalise and analyse various security properties. Differently from many classical treatments of secure multi-party computations, we always quantify security in exact terms. Although working with concrete time bounds and success probabilities is technically more demanding, it also has several advantages. As all security guarantees are quantitative, we can always compare different protocol designs. Moreover, these security guarantees also have a clear economical interpretation and it is possible to compare cryptographic and non-cryptographic solutions. The latter is extremely important in practice, since cryptographic techniques are just one possibility to achieve practical security. Also, working with exact bounds makes reasoning errors more apparent, as security proofs are less abstract and it is easier to locate false claims. The choice of topics covered in this thesis was guided by two principles. Firstly, we wanted to give a coherent overview of the secure multi-party computation that is based on exact quantification of security guarantees. Secondly, we focused on topics that emerged from the author's own research. In that sense, the thesis generalises many methodological discoveries made by the author. As surprising as it may seem, security definitions and proofs mostly utilise principles of hypothesis testing and analysis of stochastic algorithms. Thus, we start our treatment with hypothesis testing and its generalisations. In particular, we show how to quantify various security properties, using security games as tools. Next, we review basic proof techniques and explain how to structure complex proofs so they become easily verifiable. In a nutshell, we describe how to represent a proof as a game tree, where each edge corresponds to an elementary proof step. As a result, one can first verify the overall structure of a proof by looking at the syntactic changes in the game tree and only then verify all individual proof steps corresponding to the edges. The remaining part of the thesis is dedicated to various aspects of protocol design. Firstly, we discuss how to formalise various security goals, such as input-privacy, output-consistency and complete security, and how to choose a security goal that is appropriate for a specific setting. Secondly, we also explore alternatives to exact security. More precisely, we analyse connections between exact and asymptotic security models and rigorously formalise a notion of subjective security. Thirdly, we study in which conditions protocols preserve their security guarantees and how to safely combine several protocols. Although composability results are common knowledge, we look at them from a slightly different angle. Namely, it is irrational to design universally composable protocols at any cost; instead, we should design computationally efficient protocols with minimal usage restrictions. Thus, we propose a three-stage design procedure that leads to modular security proofs and minimises usage restrictions.

•Jan 1, 2008•1 citation

On Protocol Security in the Cryptographic Model

Copyright C, Jesper Buus Nielsen

It seems to be a generally acknowledged fact that you should never trust a computer and that you should trust the person operating the computer even less. This in particular becomes a problem when the party that you do not trust is one which is separated from you and is one on which you depend, e.g. because that party is the holder of some data or some capability that you need in order to operate correctly. How do you perform a given task involving interaction with other parties while allowing these parties a minimal influence on you and, if privacy is an issue, allowing them to learn as little about you as possible. This is the general problem of secure multiparty computation. The usual way of formalizing the problem is to say that a number of parties who do not trust each other wish to compute some function of their local inputs, while keeping their inputs as secret as possible and guaranteeing the correctness of the output. Both goals should be obtained even if some parties stop participating or some malevolent coalition of the parties start deviating arbitrarily from the agreed protocol. The task is further complicated by the fact that besides their mutual distrust, nor do the parties trust the channels by which they communicate. A general solution to the secure multiparty computation problem is a compiler which given any feasible function describes an efficient protocol which allows the parties to compute the function securely on their local inputs over an open network. Over the past twenty years the secure multiparty computation problem has been the subject of a large body of research, both research into the models of multiparty computation and research aimed at realizing general secure multiparty computation. The main approach to realizing secure multiparty computation has been based on verifiable secret sharing as computation, where each party holds a secret share of each input and during the execution computes secret shares of all intermediate values. This approach allows the parties to keep all inputs and intermediate values secret and to pool the shares of the output values to learn exactly these values. More recently an approach based on joint homomorphic encryption was introduced, allowing for an efficient realization of general multiparty computation secure against an eavesdropper. A joint encryption scheme is an encryption scheme where all parties can encrypt, but where it takes the participation of all parties to open an encryption. The computation then starts by all parties broadcasting encryptions of their inputs and progresses through computing encryptions of the intermediary values using the homomorphic properties of the encryption scheme. The encryptions of the outputs can then be jointly decrypted. In this dissertation we extend this approach by using threshold homomorphic encryption to provide full-fledged security against an active attacker which might control some of the parties and which might take over parties during the course of the protocol execution. As opposed to a joint encryption scheme a threshold encryption scheme only requires that a given number of the parties are operating correctly for decryption to be possible. In this dissertation we show that threshold homomorphic encryption allows to solve the secure general multiparty computation problem more efficiently than previous approaches to the problem. Starting from an open point-to-point network there is a long way to general secure multiparty computation. The dissertation contains contributions at several points along the way. In particular we investigate how to realize secure channels. We also show how threshold signature schemes can be used to efficiently realize a broadcast channel and how threshold cryptography can be used to provide the parties of the network with a source of shared randomness. All three tools are well-known to be extremely powerful resources in a network, and our principle contribution is to provide efficient realizations. The dissertation also contains contributions to the definitional part of the field of multiparty computation. Most significantly we augment the recent model of universally composable security with a formal notion of what it means for a protocol to only realize a given problem under a given restricted input-output behavior of the environment. This e.g. allows us to give the first specification of a universally composable zero-knowledge proof of membership which does not at the same time require the proof system to be a proof of knowledge.

•Jan 1, 2003•10 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.
The field of rational cryptography considers the design of cryptographic protocols in the presence of rational agents seeking to maximize local utility functions. This departs from the standard secure multiparty computation setting, where players are assumed to be either honest or malicious. We detail the construction of both a two-party and a multiparty game theoretic framework for constructing rational cryptographic protocols. Our framework specifies the utility function assumptions necessary to realize the privacy, correctness, and fairness guarantees for protocols. We demonstrate that our framework correctly models cryptographic protocols, such as rational secret sharing, where existing work considers equilibrium concepts that yield unreasonable equilibria. Similarly, we demonstrate that cryptography may be applied to the game theoretic domain, constructing an auction market not realizable in the original formulation. Additionally, we demonstrate that modeling players as rational agents allows us to design a protocol that destabilizes coalitions. Thus, we establish a mutual benefit from combining the two fields, while demonstrating the applicability of our framework to real-world market environments. We also give an application of game theory to adversarial interactions where cryptography is not necessary. Specifically, we consider adversarial machine learning, where the adversary is rational and reacts to the presence of a data miner. We give a general extension to classification algorithms that returns greater expected utility for the data miner than existing classification methods.
The design of secure protocols that implement arbitrarily desired functionalities is a major part of modern cryptography. Taking the opposite perspective, the design of any cryptographic scheme may be viewed as the design of a secure protocol for implementing a suitable functionality. Still, we believe that it makes sense to differentiate between basic cryptographic primitives (which involve little interaction) like encryption and signature schemes, on the one hand, and general cryptographic protocols, on the other hand. In this chapter we consider general results concerning secure multi –party computations, where the two –party case is an important special case. In a nutshell, these results assert that one can construct protocols for securely computing any desirable multi–party functionality (see the following terminology). Indeed, what is striking about these results is their generality, and we believe that the wonder is not diminished by the (various alternative) conditions under which these results hold. Our focus on the general study of secure multi–party computation (rather than on protocols for solving specific problems) is natural in the context of the theoretical treatment of the subject matter. We wish to highlight the importance of this general study to practice. Firstly, this study clarifies fundamental issues regarding security in a multi–party environment. Secondly, it draws the lines between what is possible in principle and what is not. Thirdly, it develops general techniques for designing secure protocols. And last, sometimes it may even yield schemes (or modules) that may be incorporated in practical systems.
The aim of this paper is to present some of the recent progress in efficient secure multiparty computation (MPC). In MPC we have a set of parties owning a set of private inputs. The par ties want to compute a function of their inputs, but they do not trust each other, therefore they need a cryptographic protocol to perform the computation in a way that 1) the output is correct and 2) cheating parties will not be able to learn any information about the honest parties inputs. Even though this problem has been formulated and essentially solved almost 30 years ago, practical solutions that can be relevant for real-world applications have been discovered only in the last few years. We will present some of these advances, trying to explain to a non-specialized audience the significance of the several existing security notions.
Secure multi-party computation (MPC) is a cryptographic primitive that lets a num- ber N of mutually distrustful parties compute a function f (x1, . . . , xN ) on their private inputs xi such that at the end of the MPC protocol, each honest party obtains the func- tion’s correct output and no adversary controlling a certain subset of parties learns any- thing about the honest parties’ inputs beyond what can be inferred from the function’s output value. In 2002, [Smi01] and [CGS02] introduced the notion of multi-party quan- tum computation (MPQC) in which arbitrary quantum circuits can be evaluated in a distributed manner, secure against a quantum adversary. Few protocols for MPQC are known. We present a fundamental study of the building blocks of MPC and MPQC in the information-theoretic setting with a focus on protocols built on top of (quantum) se- cret sharing schemes. In particular, we point out structural similarities and differences and compile an extensive list of theoretical feasibility results for the maximum number of corrupted parties within classical and quantum secret sharing and MPC protocols.
In this work, we investigate the security of interactive computations. The main emphasis is on the mathematical methodology that is needed to formalise and analyse various security properties. Differently from many classical treatments of secure multi-party computations, we always quantify security in exact terms. Although working with concrete time bounds and success probabilities is technically more demanding, it also has several advantages. As all security guarantees are quantitative, we can always compare different protocol designs. Moreover, these security guarantees also have a clear economical interpretation and it is possible to compare cryptographic and non-cryptographic solutions. The latter is extremely important in practice, since cryptographic techniques are just one possibility to achieve practical security. Also, working with exact bounds makes reasoning errors more apparent, as security proofs are less abstract and it is easier to locate false claims. The choice of topics covered in this thesis was guided by two principles. Firstly, we wanted to give a coherent overview of the secure multi-party computation that is based on exact quantification of security guarantees. Secondly, we focused on topics that emerged from the author's own research. In that sense, the thesis generalises many methodological discoveries made by the author. As surprising as it may seem, security definitions and proofs mostly utilise principles of hypothesis testing and analysis of stochastic algorithms. Thus, we start our treatment with hypothesis testing and its generalisations. In particular, we show how to quantify various security properties, using security games as tools. Next, we review basic proof techniques and explain how to structure complex proofs so they become easily verifiable. In a nutshell, we describe how to represent a proof as a game tree, where each edge corresponds to an elementary proof step. As a result, one can first verify the overall structure of a proof by looking at the syntactic changes in the game tree and only then verify all individual proof steps corresponding to the edges. The remaining part of the thesis is dedicated to various aspects of protocol design. Firstly, we discuss how to formalise various security goals, such as input-privacy, output-consistency and complete security, and how to choose a security goal that is appropriate for a specific setting. Secondly, we also explore alternatives to exact security. More precisely, we analyse connections between exact and asymptotic security models and rigorously formalise a notion of subjective security. Thirdly, we study in which conditions protocols preserve their security guarantees and how to safely combine several protocols. Although composability results are common knowledge, we look at them from a slightly different angle. Namely, it is irrational to design universally composable protocols at any cost; instead, we should design computationally efficient protocols with minimal usage restrictions. Thus, we propose a three-stage design procedure that leads to modular security proofs and minimises usage restrictions.
It seems to be a generally acknowledged fact that you should never trust a computer and that you should trust the person operating the computer even less. This in particular becomes a problem when the party that you do not trust is one which is separated from you and is one on which you depend, e.g. because that party is the holder of some data or some capability that you need in order to operate correctly. How do you perform a given task involving interaction with other parties while allowing these parties a minimal influence on you and, if privacy is an issue, allowing them to learn as little about you as possible. This is the general problem of secure multiparty computation. The usual way of formalizing the problem is to say that a number of parties who do not trust each other wish to compute some function of their local inputs, while keeping their inputs as secret as possible and guaranteeing the correctness of the output. Both goals should be obtained even if some parties stop participating or some malevolent coalition of the parties start deviating arbitrarily from the agreed protocol. The task is further complicated by the fact that besides their mutual distrust, nor do the parties trust the channels by which they communicate. A general solution to the secure multiparty computation problem is a compiler which given any feasible function describes an efficient protocol which allows the parties to compute the function securely on their local inputs over an open network. Over the past twenty years the secure multiparty computation problem has been the subject of a large body of research, both research into the models of multiparty computation and research aimed at realizing general secure multiparty computation. The main approach to realizing secure multiparty computation has been based on verifiable secret sharing as computation, where each party holds a secret share of each input and during the execution computes secret shares of all intermediate values. This approach allows the parties to keep all inputs and intermediate values secret and to pool the shares of the output values to learn exactly these values. More recently an approach based on joint homomorphic encryption was introduced, allowing for an efficient realization of general multiparty computation secure against an eavesdropper. A joint encryption scheme is an encryption scheme where all parties can encrypt, but where it takes the participation of all parties to open an encryption. The computation then starts by all parties broadcasting encryptions of their inputs and progresses through computing encryptions of the intermediary values using the homomorphic properties of the encryption scheme. The encryptions of the outputs can then be jointly decrypted. In this dissertation we extend this approach by using threshold homomorphic encryption to provide full-fledged security against an active attacker which might control some of the parties and which might take over parties during the course of the protocol execution. As opposed to a joint encryption scheme a threshold encryption scheme only requires that a given number of the parties are operating correctly for decryption to be possible. In this dissertation we show that threshold homomorphic encryption allows to solve the secure general multiparty computation problem more efficiently than previous approaches to the problem. Starting from an open point-to-point network there is a long way to general secure multiparty computation. The dissertation contains contributions at several points along the way. In particular we investigate how to realize secure channels. We also show how threshold signature schemes can be used to efficiently realize a broadcast channel and how threshold cryptography can be used to provide the parties of the network with a source of shared randomness. All three tools are well-known to be extremely powerful resources in a network, and our principle contribution is to provide efficient realizations. The dissertation also contains contributions to the definitional part of the field of multiparty computation. Most significantly we augment the recent model of universally composable security with a formal notion of what it means for a protocol to only realize a given problem under a given restricted input-output behavior of the environment. This e.g. allows us to give the first specification of a universally composable zero-knowledge proof of membership which does not at the same time require the proof system to be a proof of knowledge.