Paper 2014/209

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, and Moti Yung


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.

Available format(s)
Publication info
Preprint. Minor revision.
anonymityMPCadaptive securitydishonest majoritytwo-tier model
Contact author(s)
gelles @ cs ucla edu
2014-03-22: received
Short URL
Creative Commons Attribution


      author = {Juan A.  Garay and Ran Gelles and David S.  Johnson and Aggelos Kiayias and Moti Yung},
      title = {A Little Honesty Goes a Long Way: The Two-Tier Model for Secure Multiparty Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/209},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.