On Achieving the" Best of Both Worlds" in Secure Multiparty Computation

TitleOn Achieving the" Best of Both Worlds" in Secure Multiparty Computation
Publication TypeJournal Articles
Year of Publication2011
AuthorsIshai Y, Katz J, Kushilevitz E, Lindell Y, Petrank E
JournalSIAM Journal on Computing
Volume40
Issue1
Pagination122 - 122
Date Published2011///
Abstract

Two settings are traditionally considered for secure multiparty computation, de-pending on whether or not a majority of the parties are assumed to be honest. Existing protocols
that assume an honest majority provide “full security” (and, in particular, guarantee output delivery
and fairness) when this assumption holds, but are completely insecure if this assumption is violated.
On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee
fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether
it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously
achieves the best possible security in both the above settings. Here, we rule out this possibility (at
least for general functionalities) and show some positive results regarding what can be achieved.