Welcome to the resource topic for 2014/209
Title:
A Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty Computation
Authors: Juan A. Garay, Ran Gelles, David S. Johnson, Aggelos Kiayias, Moti Yung
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\in (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. 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.
ePrint: https://eprint.iacr.org/2014/209
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .