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

Fair and Efficient Secure Multiparty Computation with Reputation Systems.

Gilad Asharov, Yehuda Lindell, Hila Zarosim

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

Abstract. A reputation system for a set of entities is essentially a list of scores that provides a measure of the reliability of each entity in the set. The score given to an entity can be interpreted (and in the reputation system literature it often is [12]) as the probability that an entity will behave honestly. In this paper, we ask whether or not it is possible to utilize reputation systems for carrying out secure multiparty computa-tion. We provide formal definitions of secure computation in this setting, and carry out a theoretical study of feasibility. We present almost tight results showing when it is and is not possible to achieve fair secure com-putation in our model. We suggest applications for our model in settings where some information about the honesty of other parties is given. This can be preferable to the current situation where either an honest ma-jority is arbitrarily assumed, or a protocol that is secure for a dishonest majority is used and the efficiency and security guarantees (including fairness) of an honest majority are not obtained.

Related papers

On Achieving the “Best of Both Worlds” in Secure Multiparty Computation

Yuval Ishai, Jonathan I. Katz, Eyal Kushilevitz +2 more

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.

SIAM Journal on Computing•Jan 1, 2011•32 citations

Secure Multiparty Computation with Partial Fairness

Amos Beimel, Eran Omri, Ilan Orlov

A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair -- all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition -- 1/p-secure computation -- which guarantees partial fairness. For two parties, they construct 1/p-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p-secure protocols when the number of parties is constant provided that less than 2/3 of the parties are corrupt. Our protocols require that either (1) the functionality is deterministic and the size of the domain is polynomial (in the security parameter), or (2) the functionality can be randomized and the size of the range is polynomial. If the size of the domain is constant and the functionality is deterministic, then our protocol is efficient even when the number of parties is O(log log n) (where n is the security parameter). On the negative side, we show that when the number of parties is super-constant, 1/p-secure protocols are not possible when the size of the domain is polynomial.

arXiv:1011.5567•Nov 25, 2010•0 citations

A Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty Computation.

Juan A. Garay, Ran Gelles, David Johnson +2 more

Abstract. Secure multiparty computation (MPC) as a service is becoming a tangible reality. In such a service, a population of clients wish to utilize a set of servers to delegate privately and reliably a given computation on their inputs. MPC protocols have a number of desired properties including tolerating active misbehavior by some of the servers and guaranteed output delivery. A fundamental result is that in order to achieve the above, an honest majority among servers is necessary. There are settings, however, where this condition might be overly restrictive, making it important to investigate models where this impossibility result can be circumvented, allowing secure computation to be performed even when the number of malicious participants outweighs the number of honest participants. To this end, we introduce the two-tier model for MPC, where a set of m parties that are guaranteed to be honest (the first tier) remains “hidden ” within a set of n − m servers which are of dubious trustworthiness (the second tier), and where the objective is to perform MPC withstanding a number of active misbehaviors that is larger than m/2. Indeed, assuming αn of the second-tier servers are dishonest (where α ∈ (0, 1)), we present an MPC protocol that can withstand up to (1 − )(1 − α)n/2 additional faults, for any > 0 and m = ω(logn). Somewhat surprisingly, this allows the total number of faulty parties to exceed n/2 across both tiers. We demonstrate that the two-tier model naturally arises in various settings, as in the case, for example, of a resource-constrained service provider wishing to utilize a pre-existing set of servers. 1

•Jan 1, 2014•2 citations

On achieving the "best of both worlds" in secure multiparty computation

Jonathan I. Katz

Two settings are typically considered for secure multipartycomputation, depending on whether or not a majority of the partiesare assumed to be honest. Protocols designed under this assumptionprovide "full security" (and, in particular, guarantee outputdelivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security iscompletely compromised. On the other hand, protocols toleratingarbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It isnatural to wonder whether it is possible to achieve the "best ofboth worlds" : namely, a single protocol that simultaneouslyachieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, andruled out constant-round protocols of this type.

ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•70 citations

Foundations of Secure Computation: Perfect Security and Fairness

Gilad Asharov

In the setting of secure multiparty computation, several distrustful parties wish to carry out a distributed computing task on their local private data while satisfying several security properties such as correctness, privacy, independence of inputs and fairness. The aim of secure multiparty computation (MPC) is to enable the parties to carry out the computation in a secure manner, eliminating any attempt of an adversarial entity to harm the execution. The concept of secure computation is very general and fundamental in cryptography, and models any distributed computing task, including simple computations as coin-tossing and broadcast, as well as more complex tasks such as electronic auctions and anonymous transactions. In this thesis, we study two foundational aspects of secure computation: perfect security and fairness. In the first part of this thesis, we study perfect security in secure computation. A protocol that is perfectly secure cannot be broken even when the adversary has unlimited computational power and its security holds unconditionally. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full proof of these results was never published. In this thesis, we remedy this situation and provide a full proof of security of the BGW protocol. This also includes a full description of the protocol for the malicious setting. In addition to the above, we observe that by some simple and natural modifications, the BGW protocol can be significantly simplified and one of its expensive (and perhaps most complicated) subprotocols can be saved. We present a new multiplication protocol that is based on the original construction, but is simpler and achieves higher efficiency. In the second part of this thesis, we study fairness in secure two party computation. Informally, the fairness property guarantees that if one party receives its output, then the other party does too. The well-known impossibility result of Cleve (STOC 1986) implies that, in general, it is impossible to securely compute a function with complete fairness without an honest majority. Until recently, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) Boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. We focus on this question and give both positive and negative results. We first characterize

•Jan 1, 2014•0 citations

Complete Fairness in Secure Two-Party Computation

Steven Gordon, Carmit Hazay, Jonathan I. Katz +1 more

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting. We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.

Journal of the ACM•Dec 1, 2011•72 citations
Abstract. A reputation system for a set of entities is essentially a list of scores that provides a measure of the reliability of each entity in the set. The score given to an entity can be interpreted (and in the reputation system literature it often is [12]) as the probability that an entity will behave honestly. In this paper, we ask whether or not it is possible to utilize reputation systems for carrying out secure multiparty computa-tion. We provide formal definitions of secure computation in this setting, and carry out a theoretical study of feasibility. We present almost tight results showing when it is and is not possible to achieve fair secure com-putation in our model. We suggest applications for our model in settings where some information about the honesty of other parties is given. This can be preferable to the current situation where either an honest ma-jority is arbitrarily assumed, or a protocol that is secure for a dishonest majority is used and the efficiency and security guarantees (including fairness) of an honest majority are not obtained.
Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.
A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair -- all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition -- 1/p-secure computation -- which guarantees partial fairness. For two parties, they construct 1/p-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p-secure protocols when the number of parties is constant provided that less than 2/3 of the parties are corrupt. Our protocols require that either (1) the functionality is deterministic and the size of the domain is polynomial (in the security parameter), or (2) the functionality can be randomized and the size of the range is polynomial. If the size of the domain is constant and the functionality is deterministic, then our protocol is efficient even when the number of parties is O(log log n) (where n is the security parameter). On the negative side, we show that when the number of parties is super-constant, 1/p-secure protocols are not possible when the size of the domain is polynomial.
Abstract. Secure multiparty computation (MPC) as a service is becoming a tangible reality. In such a service, a population of clients wish to utilize a set of servers to delegate privately and reliably a given computation on their inputs. MPC protocols have a number of desired properties including tolerating active misbehavior by some of the servers and guaranteed output delivery. A fundamental result is that in order to achieve the above, an honest majority among servers is necessary. There are settings, however, where this condition might be overly restrictive, making it important to investigate models where this impossibility result can be circumvented, allowing secure computation to be performed even when the number of malicious participants outweighs the number of honest participants. To this end, we introduce the two-tier model for MPC, where a set of m parties that are guaranteed to be honest (the first tier) remains “hidden ” within a set of n − m servers which are of dubious trustworthiness (the second tier), and where the objective is to perform MPC withstanding a number of active misbehaviors that is larger than m/2. Indeed, assuming αn of the second-tier servers are dishonest (where α ∈ (0, 1)), we present an MPC protocol that can withstand up to (1 − )(1 − α)n/2 additional faults, for any > 0 and m = ω(logn). Somewhat surprisingly, this allows the total number of faulty parties to exceed n/2 across both tiers. We demonstrate that the two-tier model naturally arises in various settings, as in the case, for example, of a resource-constrained service provider wishing to utilize a pre-existing set of servers. 1
Two settings are typically considered for secure multipartycomputation, depending on whether or not a majority of the partiesare assumed to be honest. Protocols designed under this assumptionprovide "full security" (and, in particular, guarantee outputdelivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security iscompletely compromised. On the other hand, protocols toleratingarbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It isnatural to wonder whether it is possible to achieve the "best ofboth worlds" : namely, a single protocol that simultaneouslyachieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, andruled out constant-round protocols of this type.
In the setting of secure multiparty computation, several distrustful parties wish to carry out a distributed computing task on their local private data while satisfying several security properties such as correctness, privacy, independence of inputs and fairness. The aim of secure multiparty computation (MPC) is to enable the parties to carry out the computation in a secure manner, eliminating any attempt of an adversarial entity to harm the execution. The concept of secure computation is very general and fundamental in cryptography, and models any distributed computing task, including simple computations as coin-tossing and broadcast, as well as more complex tasks such as electronic auctions and anonymous transactions. In this thesis, we study two foundational aspects of secure computation: perfect security and fairness. In the first part of this thesis, we study perfect security in secure computation. A protocol that is perfectly secure cannot be broken even when the adversary has unlimited computational power and its security holds unconditionally. One of the most fundamental results of secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any n-party functionality can be computed with perfect security, in the private channels model. When the adversary is semi-honest this holds as long as t < n/2 parties are corrupted, and when the adversary is malicious this holds as long as t < n/3 parties are corrupted. Unfortunately, a full proof of these results was never published. In this thesis, we remedy this situation and provide a full proof of security of the BGW protocol. This also includes a full description of the protocol for the malicious setting. In addition to the above, we observe that by some simple and natural modifications, the BGW protocol can be significantly simplified and one of its expensive (and perhaps most complicated) subprotocols can be saved. We present a new multiplication protocol that is based on the original construction, but is simpler and achieves higher efficiency. In the second part of this thesis, we study fairness in secure two party computation. Informally, the fairness property guarantees that if one party receives its output, then the other party does too. The well-known impossibility result of Cleve (STOC 1986) implies that, in general, it is impossible to securely compute a function with complete fairness without an honest majority. Until recently, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) Boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. We focus on this question and give both positive and negative results. We first characterize
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting. We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.