Universally composable (UC) multi-party computation has been studied in two settings. When a majority of parties are honest, UC multi-party computation is possible without any assumptions. Without a majority of honest parties, UC multi-party computation is impossible in the plain model, but feasibility results have been obtained in various augmented models. The most popular such model posits a
common reference string
(CRS) available to parties executing the protocol.
In either of the above settings, some
regarding the protocol execution is made: i.e., that many parties are honest in the first case, or that a legitimately-chosen string is available in the second. If this assumption is incorrect then all security is lost.
A natural question is whether it is possible to design protocols secure if
of these assumptions holds, i.e., a protocol which is secure if
players are dishonest
if up to
players are dishonest but the CRS is chosen in the prescribed manner. We show that such protocols exist if and only if