On achieving the "best of both worlds" in secure multiparty computation

TitleOn achieving the "best of both worlds" in secure multiparty computation
Publication TypeConference Papers
Year of Publication2007
AuthorsKatz J
Conference NameProceedings of the thirty-ninth annual ACM symposium on Theory of computing
Date Published2007///
Conference LocationNew York, NY, USA
ISBN Number978-1-59593-631-8
KeywordsCOMPUTATION, secure

Two settings are typically considered for secure multipartycomputation, depending on whether or not a majority of the partiesare assumed to be honest. Protocols designed under this assumptionprovide "full security" (and, in particular, guarantee outputdelivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security iscompletely compromised. On the other hand, protocols toleratingarbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It isnatural to wonder whether it is possible to achieve the "best ofboth worlds" : namely, a single protocol that simultaneouslyachieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, andruled out constant-round protocols of this type. As our main result, we completely settle the question by ruling outprotocols using any (expected) polynomial number of rounds. Given this stark negative result, we then ask what can be achieved if we are willing to assume simultaneous message transmission (or, equivalently, a non-rushing adversary). In this setting, we show that impossibility still holdsfor logarithmic-round protocols. We also show, for any polynomialp, a protocol (whose round complexity depends on p) that can be simulated to within closeness O(1/p).