A little honesty goes a long way: The two-tier model for secure multiparty computation
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
International Association for Cryptologic Research 2015. Afundamental result in securemultiparty computation (MPC) is that in order to achieve full security, it is necessary that amajority of the partiesbehave honestly.There are settings, however,where the condition of an honest majority might be overly restrictive, and there is a need to define and investigate other plausible adversarial models in order to circumvent the above impossibility. To this end, we introduce the two-tier model for MPC, where some small subset of servers is guaranteed to be honest at the beginning of the computation (the first tier), while the corruption state of the other servers (the second tier) is unknown. The two-tier model naturally arises in various settings, such as for example when a service provider wishes to utilize a large pre-existing set of servers, while being able to trust only a small fraction of them. The first tier is responsible for performing the secure computation while the second tier serves as a disguise: using novel anonymization techniques, servers in the first tier remain undetected to an adaptive adversary, preventing a targeted attack on these critical servers. Specifically, given n servers and assuming n of them are corrupt at the onset (where (0, 1)), we present an MPC protocol that can withstand an optimal amount of less than (1)n/2 additional adaptive corruptions, provided the first tier is of size (log n). This allows us to perform MPC in a fully secure manner even when the total number of corruptions exceeds n/2 across both tiers, thus evading the honest majority requirement.
name of conference
Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I
