IACR News item: 22 March 2014
Juan A. Garay, Ran Gelles, David S. Johnson, Aggelos Kiayias, Moti Yung
ePrint Reportoverly 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.
Additional news items may be found on the IACR news page.