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

Rationality and Adversarial Behavior in Multi-party Computation (Extended Abstract)

Anna Lysyanskaya, Nikos Triandopoulos

Published Jan 1, 2006• 5 citations
OpenAlex

Abstract

We study multi-party computation in the model where none of n participating parties are honest: they are either rational, acting in their selfish interest to maximize their utility, or adversarial, acting arbitrarily. In this new model, which we call the mixed-behavior model, we define a class of functions that can be computed in the presence of an adversary using a trusted mediator. We then give a protocol that allows the rational parties to emulate the mediator and jointly compute the function such that (1) assuming that each rational party prefers that it learns the output while others do not, no rational party has an incentive to deviate from the protocol; and (2) the rational parties are protected from a malicious adversary controlling ⌈n/2⌉ − 2 of the participants: the 2 adversary can only either cause all rational participants to abort (so no one learns the function they are trying to compute), or can only learn whatever information is implied by the output of the function.

Related papers

New rational parties relying on reputation

Yilei Wang, Zhe Liu, Qiuliang Xu

In this paper, we redefine the utilities considering other parts such as reputation in order to give rational parties incentives to participate in the protocol and finally get the correct outputs. The most distinct contribution of this paper is the proposal of rational covert adversaries whose behaviors are combinations of rational parties and covert adversaries. Finally, given proper parameters, we prove that all parties have incentives to participate in the rational secure computation protocol. Copyright © 2013 John Wiley & Sons, Ltd.

Security and Communication Networks•Nov 28, 2013•8 citations

A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority

Yehuda Lindell, Ariel Nof

Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 27, 2017•96 citations

On the Computational Overhead of MPC with Dishonest Majority

Jesper Buus Nielsen, Samuel Ranellucci

We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt $$t < c n$$ of the parties for some given $$c \in [0,1)$$ . In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all $$c < 1$$ . Prior to our result it was only known how to get poly-logarithmic overhead for $$c < \frac{1}{2}$$ . We therefore significantly extend the area where we can do secure multiparty computation with poly-logarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all c make a protocol for which there exists $$d > 0$$ such that if at most dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.

Lecture notes in computer science•Jan 1, 2017•7 citations

Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract).

Ran Canetti, Rafail Ostrovsky

) Ran Canetti Rafail Ostrovsky y April 28, 1999 Abstract In a secure multi-party computation a set of mutually distrustful parties interact in order to evaluate a pre-defined function of their inputs, without revealing the inputs to each other. In this scenario, the trust in other parties should be minimal. In the classic formulation of this problem, most of the parties are trusted to exactly follow the prescribed protocol, except for a limited number of parties that are corrupted by a centralized adversary and are allowed to deviate from the protocol in an arbitrary way. However, an assumption of a totally honest behavior of most parties can not be verified. In particular, if an "honest-looking" party diverges from its protocol in a way that is indistinguishable from a totally honest player, it can do so with "impunity". In this paper, we consider the situation where all parties (even uncorrupted ones) may deviate from their protocol in arbitrary ways, under the sole restriction ...

•Jan 1, 1999•24 citations

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

Secure Two Party Computation

Kannan Balasubramanian

The goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.

Advances in information security, privacy, and ethics book series•Aug 16, 2017•2 citations
We study multi-party computation in the model where none of n participating parties are honest: they are either rational, acting in their selfish interest to maximize their utility, or adversarial, acting arbitrarily. In this new model, which we call the mixed-behavior model, we define a class of functions that can be computed in the presence of an adversary using a trusted mediator. We then give a protocol that allows the rational parties to emulate the mediator and jointly compute the function such that (1) assuming that each rational party prefers that it learns the output while others do not, no rational party has an incentive to deviate from the protocol; and (2) the rational parties are protected from a malicious adversary controlling ⌈n/2⌉ − 2 of the participants: the 2 adversary can only either cause all rational participants to abort (so no one learns the function they are trying to compute), or can only learn whatever information is implied by the output of the function.
In this paper, we redefine the utilities considering other parts such as reputation in order to give rational parties incentives to participate in the protocol and finally get the correct outputs. The most distinct contribution of this paper is the proposal of rational covert adversaries whose behaviors are combinations of rational parties and covert adversaries. Finally, given proper parameters, we prove that all parties have incentives to participate in the rational secure computation protocol. Copyright © 2013 John Wiley & Sons, Ltd.
Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The two classic adversary models considered are semi-honest (where the adversary follows the protocol specification but tries to learn more than allowed by examining the protocol transcript) and malicious (where the adversary may follow any arbitrary attack strategy). Protocols for semi-honest adversaries are often far more efficient, but in many cases the security guarantees are not strong enough.
We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt t<cnt < c nt<cn of the parties for some given c∈[0,1)c \in [0,1)c∈[0,1) . In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all c<1c < 1c<1 . Prior to our result it was only known how to get poly-logarithmic overhead for c<12c < \frac{1}{2}c<21​ . We therefore significantly extend the area where we can do secure multiparty computation with poly-logarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all c make a protocol for which there exists d>0d > 0d>0 such that if at most dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.
) Ran Canetti Rafail Ostrovsky y April 28, 1999 Abstract In a secure multi-party computation a set of mutually distrustful parties interact in order to evaluate a pre-defined function of their inputs, without revealing the inputs to each other. In this scenario, the trust in other parties should be minimal. In the classic formulation of this problem, most of the parties are trusted to exactly follow the prescribed protocol, except for a limited number of parties that are corrupted by a centralized adversary and are allowed to deviate from the protocol in an arbitrary way. However, an assumption of a totally honest behavior of most parties can not be verified. In particular, if an "honest-looking" party diverges from its protocol in a way that is indistinguishable from a totally honest player, it can do so with "impunity". In this paper, we consider the situation where all parties (even uncorrupted ones) may deviate from their protocol in arbitrary ways, under the sole restriction ...
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 goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.