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.
Category / Keywords: anonymity, MPC, adaptive security, dishonest majority, two-tier model Date: received 21 Mar 2014, last revised 21 Mar 2014 Contact author: gelles at cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20140322:193738 (All versions of this report) Discussion forum: Show discussion | Start new discussion