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 Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty Computation

Juan A. Garay, Ran Gelles, David S. Johnson, Aggelos Kiayias, Moti M. Yung

Published Jan 1, 2015• 6 citations
Publisher
DOI
10.1007/978-3-662-46494-6_7

Related papers

Secure Multiparty Computation without One-way Functions.

Dima Yu. Grigoriev, Vladimir Shpilrain

FLAP•Jan 1, 2017•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

From Fairness to Full Security in Multiparty Computation

Ran Cohen, Iftach Haitner, Eran Omri +1 more

Lecture notes in computer science•Jan 1, 2018•9 citations

Fair and Efficient Secure Multiparty Computation with Reputation Systems.

Gilad Asharov, Yehuda Lindell, Hila Zarosim

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.

•Jan 1, 2013•0 citations

From Fairness to Full Security in Multiparty Computation

Ran Cohen, Iftach Haitner, Eran Omri +1 more

arXiv:2105.00962•Journal of Cryptology•Dec 7, 2021•11 citations

When Is a Semi-honest Secure Multiparty Computation Valuable?

Radhika Bhargava, Chris Clifton

Lecture notes in computer science•Jan 1, 2019•1 citation
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
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.