Universally Composable Multi-party Computation with an Unreliable Common Reference String

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

assumption

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

either one

of these assumptions holds, i.e., a protocol which is secure if

either

at most

s

players are dishonest

or

if up to

t

 > 

s

players are dishonest but the CRS is chosen in the prescribed manner. We show that such protocols exist if and only if

s

 + 

t

 < 

n

.