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 \alpha n of the second-tier servers are dishonest (where \alpha belongs to (0,1)), we present an MPC protocol that can withstand up to (1-\epsilon)(1-\alpha)n/2 additional faults, for any \epsilon>0 and m = \omega(\log n). Somewhat surprisingly, this allows the total number of faulty parties to exceed n/2 across both tiers.